A linear algorithm for determining the separation of convex polyhedra

David P. Dobkin, David G. Kirkpatrick

Research output: Contribution to journalArticle

134 Scopus citations

Abstract

The separation of two convex polyhedra is defined to be the minimum distance from a point (not necessarily an extreme point) of one to a point of the other. A linear time algorithm is presented for constructing a pair of points that realize the separation of two convex polyhedra in three dimensions. This algorithm is based on a simple hierarchical description of polyhedra that is of interest in its own right. The result provides a linear algorithm for detecting the intersection of convex polyhedra. Separation and intersection detection algorithms have applications in clustering, the intersection of half-spaces, linear programming, and robotics.

Original languageEnglish (US)
Pages (from-to)381-392
Number of pages12
JournalJournal of Algorithms
Volume6
Issue number3
DOIs
StatePublished - Sep 1985

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A linear algorithm for determining the separation of convex polyhedra'. Together they form a unique fingerprint.

  • Cite this