# The ICICS/CS Reading Room

## UBC CS TR-83-05 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.