2020/11/23 by Ovidiu Daescu, Daescu, Ovidiu, Ka Yaw Teo +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2011.11672
openalex publication_date 2020/11/23 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
An articulated probe is modeled in the plane as two line segments, ab and\nbc, joined at b, with ab being very long, and bc of some small length\nr. We investigate a trajectory planning problem involving the articulated\ntwo-segment probe where the length r of bc can be customized. Consider a\nset P of simple polygonal obstacles with a total of n vertices, a target\npoint t located in the free space such that t cannot see to infinity, and a\ncircle S centered at t enclosing P. The probe initially resides outside\nS, with ab and bc being collinear, and is restricted to the following\nsequence of moves: a straight line insertion of abc into S followed by a\nrotation of bc around b. The goal is to compute a feasible\nobstacle-avoiding trajectory for the probe so that, after the sequence of\nmoves, c coincides with t.\n We prove that, for n line segment obstacles, the smallest length r for\nwhich there exists a feasible probe trajectory can be found in\nO(n2+\ε) time using O(n2+\ε) space, for any constant\n\ε > 0. Furthermore, we prove that all values r for which a feasible\nprobe trajectory exists form O(n2) intervals, and can be computed in\nO(n5/2) time using O(n2+\ε) space. We also show that, for a\ngiven r, the feasible trajectory space of the articulated probe can be\ncharacterized by a simple arrangement of complexity O(n2), which can be\nconstructed in O(n2) time. To obtain our solutions, we design efficient data\nstructures for a number of interesting variants of geometric intersection and\nemptiness query problems.\n