Fast detection of polyhedral intersection

David P. Dobkin, David G. Kirkpatrick

Research output: Contribution to journalArticlepeer-review

127 Scopus citations


Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log2 n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

Original languageEnglish (US)
Pages (from-to)241-253
Number of pages13
JournalTheoretical Computer Science
Issue number3
StatePublished - 1983

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Fast detection of polyhedral intersection'. Together they form a unique fingerprint.

Cite this