Retraction

摘要

The two-dimensional Movers' Problem may be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional robot system B, determine whether 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 straightline segment, running respectively in time 0(n log n) and 0(n2 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 generalizes the notion of Voronoi diagram to the 3-dimensional configuration space of the moving segment.