A `retraction' method for planning the motion of a disc

A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalised Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log(n)) algorithm for planning an obstacle-avoiding motion in two domensions for a single circular disc amid polygonal obstacles.