Combinatorial complexity of translating a box in polyhedral 3-space

Dan Halperin, Chee Keng Yap

Research output: Contribution to journalArticlepeer-review


We study the space of free translations of a box amidst polyhedral obstacles with n vertices. We show that the combinatorial complexity of this space is O(n2α(n)), where α(n) is the inverse Ackermann function. Our bound is within an α(n) factor off the lower bound, and it constitutes an improvement of almost an order of magnitude over the best previously known (and naive) bound for this problem, O(n3). For the case of a convex polygon of fixed (constant) size translating in the same setting (namely, a two-dimensional polygon translating in three-dimensional space), we show a tight bound Θ(n2α(n)) on the complexity of the free space.

Original languageEnglish (US)
Pages (from-to)181-196
Number of pages16
JournalComputational Geometry: Theory and Applications
Issue number3
StatePublished - Feb 1998


  • Computational geometry
  • Minkowski sums
  • Motion planning

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Combinatorial complexity of translating a box in polyhedral 3-space'. Together they form a unique fingerprint.

Cite this