Computing the intersection-depth of polyhedra

David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

Research output: Contribution to journalArticlepeer-review

111 Scopus citations


Given two intersecting polyhedra P, Q and a direction d, find the smallest translation of Q along d that renders the interiors of P and Q disjoint. The same problem can also be posed without specifying the direction, in which case the minimum translation over all directions is sought. These are fundamental problems that arise in robotics and computer vision. We develop techniques for implicitly building and searching convolutions and apply them to derive efficient algorithms for these problems.

Original languageEnglish (US)
Pages (from-to)518-533
Number of pages16
Issue number6
StatePublished - Jun 1993

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Intersection
  • Minkowski sum
  • Plane sweep
  • Polyhedral hierarchy
  • Ray shooting


Dive into the research topics of 'Computing the intersection-depth of polyhedra'. Together they form a unique fingerprint.

Cite this