An optimal algorithm for Euclidean shortest paths in the plane

An optimal algorithm for Euclidean shortest paths in the plane

0.00 Avg rating0 Votes
Article ID: iaor20002983
Country: United States
Volume: 28
Issue: 6
Start Page Number: 2215
End Page Number: 2256
Publication Date: Jun 1999
Journal: SIAM Journal On Computing
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.