Emily Kyle Fox

We consider a new trajectory planning problem involving a simple articulated probe. The probe is modeled as two line segments \(ab\) and \(bc\), with a joint at the common point \(b\), where \(bc\) is of fixed length \(r\) and \(ab\) is of arbitrarily large length. Initially, \(ab\) and \(bc\) are collinear. Given a set of obstacles in the form of \(n\) line segments and a target point \(t\), the probe is to first be inserted in straight line, followed possibly by a rotation of \(bc\), so that in the final configuration \(c\) coincides with \(t\), all while avoiding intersections with the obstacles. We prove that a feasible probe trajectory can be determined in \(O(n^2 \log n)\) time using \(O(n \log n)\) space (in fact, our algorithm finds a set of “extremal” feasible configurations). We also show that, for any constant \(\delta > 0\), a feasible probe trajectory with a clearance \(\delta\) can be determined in \(O(n^2 \log n)\) time using \(O(n^2)\) space. Furthermore, we demonstrate that our algorithms can be extended to the case of \(h\) polygonal obstacles, where we can find a feasible solution in \(O(n^2 + h^2 \log n)\) time using \(O(n \log n)\) space when there is no clearance requirement or \(O(n^2)\) space otherwise. In the process of describing the algorithms, we address and solve some other interesting problems, such as circular sector emptiness queries and a special case of circular arc ray shooting queries for line segments and circular arcs in the plane.

This work contains results from "Trajectory planning for an articulated probe". Joint with Ovidiu Daescu and Ka Yaw Teo. Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG), 296–303, 2018