A "retraction" method for planning the motion of a disc

Colm Ó'Dúnlaing, Chee K. Yap

Research output: Contribution to journalArticlepeer-review


A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized 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 of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.

Original languageEnglish (US)
Pages (from-to)104-111
Number of pages8
JournalJournal of Algorithms
Issue number1
StatePublished - Mar 1985

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'A "retraction" method for planning the motion of a disc'. Together they form a unique fingerprint.

Cite this