Technical Reports

The ICICS/CS Reading Room

UBC CS TR-83-05 Summary

A Linear Algorithm for Determining the Separation of Convex Polyhedra, January 1983 David P. Dobkin and David G. Kirkpatrick

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. .br 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.

If you have any questions or comments regarding this page please send mail to