Shortest Paths Among Obstacles in the Plane Revisited

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. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(n log n) is a lower bound. It has been an open problem for over two decades whether the space can be reduced to O(n). In this paper, we settle it by solving the problem in O(n log n) time and O(n) space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point s in O(n log n) time and O(n) space, such that given any query point t, the length of a shortest path from s to t can be computed in O(log n) time and a shortest path can be produced in additional time linear in the number of edges of the path.