Deforming Curves in the Plane for Tethered-robot Motion Planning
Susan Hert, V. Lumelsky · 1996
We present an algorithm that deforms a given set of polygonal lines (polylines) defined on a set of 2n vertices into the new set of polylines that results from one of the vertices moving along a straight line to a new point in the plane, creating bends in the polylines intersected by the line of motion. The algorithm has applications in robotics, where the moving point is one of n robots in the plane and the polylines are representations of taut tethers attached to the robots. The algorithm runs in O(kn 2 ) time, where k is the maximum number of line segments a polyline may have. The algorithm makes use of work presented in [8], which requires that a triangulation of the set of polyline vertices be maintained. When the polyline vertices change, so must the triangulation. Also presented here is a new triangulation algorithm and data structure that allows for easy insertion and deletion of triangle vertices. The data structure requires O(n) space and allows vertices to be inserted in ...