2020/11/23 by Ovidiu Daescu, Daescu, Ovidiu, Ka Yaw Teo +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2011.11685
openalex publication_date 2020/11/23 · openalex created_date 2020/12/07 · openalex updated_date 2026/07/28
Consider an input consisting of a set of n disjoint triangular obstacles in\n\ℝ3 and a target point t in the free space, all enclosed by a\nlarge sphere S of radius R centered at t. An articulated probe is modeled\nas two line segments ab and bc connected at point b. The length of ab\ncan be equal to or greater than R, while bc is of a given length r \≤\nR. The probe is initially located outside S, assuming an unarticulated\nconfiguration, in which ab and bc are collinear and b \∈ ac. The goal is\nto find a feasible (obstacle-avoiding) probe trajectory to reach t, with the\ncondition that the probe is constrained by the following sequence of moves -- a\nstraight-line insertion of the unarticulated probe into S, possibly followed\nby a rotation of bc at b for at most \π/2 radians, so that c coincides\nwith t.\n We prove that if there exists a feasible probe trajectory, then a set of\nextremal feasible trajectories must be present. Through careful case analysis,\nwe show that these extremal trajectories can be represented by O(n4)\ncombinatorial events. We present a solution approach that enumerates and\nverifies these combinatorial events for feasibility in overall\nO(n4+\ε) time using O(n4+\ε) space, for any constant\n\ε > 0. The enumeration algorithm is highly parallel, considering that\neach combinatorial event can be generated and verified for feasibility\nindependently of the others. In the process of deriving our solution, we design\nthe first data structure for addressing a special instance of circular sector\nemptiness queries among polyhedral obstacles in three dimensional space, and\nprovide a simplified data structure for the corresponding emptiness query\nproblem in two dimensions.\n