TY - GEN
T1 - Shortest paths among obstacles in the plane
AU - Mitchell, Joseph S.B.
PY - 1993
Y1 - 1993
N2 - We give a subquadratic (O(n5/3+ε) time and space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worstcase. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in time O(log n). The algorithm extends to the case of multiple source points, yielding a geodesic Voronoi diagram within the same time bound.
AB - We give a subquadratic (O(n5/3+ε) time and space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worstcase. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in time O(log n). The algorithm extends to the case of multiple source points, yielding a geodesic Voronoi diagram within the same time bound.
UR - https://www.scopus.com/pages/publications/0027800335
U2 - 10.1145/160985.161156
DO - 10.1145/160985.161156
M3 - Conference contribution
AN - SCOPUS:0027800335
SN - 0897915828
SN - 9780897915823
T3 - Proceedings of the 9th Annual Symposium on Computational Geometry
SP - 308
EP - 317
BT - Proceedings of the 9th Annual Symposium on Computational Geometry
PB - Publ by ACM
T2 - Proceedings of the 9th Annual Symposium on Computational Geometry
Y2 - 19 May 1993 through 21 May 1993
ER -