A New Algorithm for Euclidean Shortest Paths in the Plane
Haitao Wang · Journal of the ACM · 2023
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (inSIAM Journal on Computing, 1999) gave an algorithm ofO(nlogn) time andO(nlogn) space, wherenis the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space toO(n)while the runtime of the algorithm is stillO(nlogn). In this article, we present a new algorithm ofO(n+hlogh) time andO(n)space, provided that a triangulation of the free space is given, wherehis the number of obstacles. The algorithm is better than the previous work whenhis relatively small. Our algorithm builds a shortest path map for a source pointsso that given any query pointt, the shortest path length fromstotcan be computed inO(logn) time and a shortests-tpath can be produced in additional time linear in the number of edges of the path.