A Linear Algorithm for Determining the Separation of Convex Polyhedra

David P. Dobkin and David G. Kirkpatrick
Publishing date
January 1983

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. We present a linear algorithm for constructing a pair of points that realize the separation of two convex polyhedra in three dimensions. Our algorithm is based on a simple hierarchical description of polyhedra that is of interest in its own right. Our 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.