Generalized voronoi diagrams for moving a ladder. I: Topological analysis

Colm Ó'Dunlaing, Micha Sharir, Chee K. Yap

Research output: Contribution to journalArticlepeer-review


Given a bounded open subset Ω of the plane whose boundary is the union of finitely many polygons, and a real number d > 0, a manifold FP (the [free placements]) may be defined as the set of placements of a closed oriented line‐segment B (a [ladder]) of length d inside Ω. FP is a three‐dimensional manifold. A [Voronoi complex] in this manifold, a two‐dimensional cell complex, is defined by analogy with the classical geometric construction in the plane; within this complex a one‐dimensional subcomplex N, called the skeleton, is defined. It is shown that every component of FP contains a unique component of N, and canonical motions are given to move the ladder to placements within N. In this way, general motion planning is reduced to searching in a suitable representation of N as a (combinatorial) graph. Efficient construction of N is described in a companion paper.

Original languageEnglish (US)
Pages (from-to)423-483
Number of pages61
JournalCommunications on Pure and Applied Mathematics
Issue number4
StatePublished - Jul 1986

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Generalized voronoi diagrams for moving a ladder. I: Topological analysis'. Together they form a unique fingerprint.

Cite this