Computing the intersection-depth of polyhedra

David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

Research output: Contribution to journalArticle

102 Scopus citations

Abstract

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
JournalAlgorithmica
Volume9
Issue number6
DOIs
StatePublished - Jun 1 1993

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

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

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

  • Cite this

    Dobkin, D., Hershberger, J., Kirkpatrick, D., & Suri, S. (1993). Computing the intersection-depth of polyhedra. Algorithmica, 9(6), 518-533. https://doi.org/10.1007/BF01190153