Optimal shortest path queries in a simple polygon
type: Item
instance of: scholarly article
title: Optimal shortest path queries in a simple polygon
zbMATH Open document ID: 0681.68065
DOI: 10.1016/0022-0000(89)90041-X
author: Leonidas Guibas
author: John Hershberger
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: The paper focuses on a simple version of the Euclidean shortest path problem: moving a point inside a simple polygon with n sides. It shows how to preprocess the polygon P so that, given two query points p and q inside the polygon, the Euclidean length of the shortest path inside P from p to q can be found in sublinear time 0(log n). The path itself must be polygonal. The paper gives a data structure that supports such shortest path queries when both endpoints are part of the query. The preprocessing phase gives a hierarchy of nested subpolygons over an underlying triangulation, such that any shortest path crosses a small number of subpolygons only. So preprocessing consists of triangulation plus a linear amount of additional work. Interesting applications and extensions are discussed at the end of the paper (disk moving, relative convex hulls).
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4115970
zbMATH Keywords: computational geometry
zbMATH Keywords: simple polygons
zbMATH Keywords: shortest path moving
reviewed by: Hans-Dietrich Hecker
MaRDI profile type: Publication
cites work: Geometric applications of a matrix-searching algorithm
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Maintenance of configurations in the plane
cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
full work available at URL: 0022-0000(89)90041-x
OpenAlex ID: W2038699153
Recommended article: Q4763413
Recommended article: Shortest Path Queries in Polygonal Domains
Recommended article: AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
Recommended article: \(L_{1}\) shortest path queries in simple polygons
Recommended article: A new data structure for shortest path queries in a simple polygon
Recommended article: Approximate Shortest Paths in Simple Polyhedra
Recommended article: Optimal Shortest Path and Minimum-Link Path Queries between Two Convex Polygons inside a Simple Polygonal Obstacle
Recommended article: Shortest path in a polygon using sublinear space
Recommended article: Shortest Path in a Polygon using Sublinear Space.
Recommended article: Query-point visibility constrained shortest paths in simple polygons
description: scientific article; zbMATH DE number 4115970