2015/04/26 by Joseph S. B. Mitchell, Mitchell, Joseph S. B., Valentin Polishchuk +5
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.1504.06842
openalex publication_date 2015/04/26 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
We consider the problem of finding minimum-link rectilinear paths in rectilinear polygonal domains in the plane. A path or a polygon is rectilinear if all its edges are axis-parallel. Given a set P of h pairwise-disjoint rectilinear polygonal obstacles with a total of n vertices in the plane, a minimum-link rectilinear path between two points is a rectilinear path that avoids all obstacles with the minimum number of edges. In this paper, we present a new algorithm for finding minimum-link rectilinear paths among P. After the plane is triangulated, with respect to any source point s, our algorithm builds an O(n)-size data structure in O(n+hlog h) time, such that given any query point t, the number of edges of a minimum-link rectilinear path from s to t can be computed in O(log n) time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithm computes such a data structure in O(nlog n) time.