An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (6), 2215-2256
- https://doi.org/10.1137/s0097539795289604
Abstract
We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources.Keywords
This publication has 15 references indexed in Scilit:
- Computing minimum length paths of a given homotopy classComputational Geometry, 1994
- An Output-Sensitive Algorithm for Computing Visibility GraphsSIAM Journal on Computing, 1991
- There are planar graphs almost as good as the complete graphJournal of Computer and System Sciences, 1989
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Visibility of disjoint polygonsAlgorithmica, 1986
- Optimal Point Location in a Monotone SubdivisionSIAM Journal on Computing, 1986
- Euclidean shortest paths in the presence of rectilinear barriersNetworks, 1984
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983
- A note on two problems in connexion with graphsNumerische Mathematik, 1959