A linear algorithm for determining the separation of convex polyhedra

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.