Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram

Colm Ó'Dúnlaing, Micha Sharir, Chee Yap

Research output: Contribution to journalArticlepeer-review


We present a collection of algorithms, all running in time O(n 2 log n α (n) o(α(n)3)) for some fixed integer s(where α(n) is the inverse Ackermann's function), for constructing a skeleton representation of a suitably generalized "Voronoi diagram" for a ladder moving in a two-dimensional space bounded by polygonal barriers consisting of n line segments. This diagram, which is a two-dimensional subcomplex of the dimensional configuration space of the ladder, is introduced and analyzed in a companion paper by the present authors. The construction of the diagram described in this paper yields a motion-planning algorithm for the ladder which runs within the same time bound given above.

Original languageEnglish (US)
Pages (from-to)27-59
Number of pages33
Issue number1-4
StatePublished - Nov 1987


  • Configuration space
  • Motion planning
  • Moving ladder
  • Robotics
  • Voronoi diagram

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram'. Together they form a unique fingerprint.

Cite this