A new algorithm for Euclidean shortest paths in the plane

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 [SIAM J. Comput. 1999] gave an algorithm of O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri's algorithm, Wang [SODA 2021] reduced the space to O(n) while the runtime of the algorithm is still O(n log n). In this paper, we present a new algorithm of O(n + h log h) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. The algorithm, which improves the previous work when h = o(n), is optimal in both time and space as Ω(n + h log h) is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point s, so that given any query point t, the shortest path length from s to t can be computed in O(log n) time and a shortest s-t path can be produced in additional time linear in the number of edges of the path.