Retraction: a new approach to motion-planning

The two-dimensional Mover's problem can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional robot system B, determine wheter one can move B from a given placement to another without touching any obstacle, and plan such a motion when one exists. Efficient algorithms are presented for the two special cases in which B is either a disc or a directed line-segment, running respectively in time O(nlog(n) and O(n²log(n)log*(n).

To solve the problem for a disc, one uses the planar Voronoi diagram determined by the obstacles. In the case of a line-segment, one generalises the notion of Voronoi diagram to the 3-dimensional configuration space of the moving segment.