2020/10/18 by Haitao Wang, Wang, Haitao · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2010.09115
openalex publication_date 2020/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nlog n) time and O(nlog n) space, where n is the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(nlog 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(nlog 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(nlog 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.