An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra

Abstract:

We describe a linear-time algorithm for computing the intersection of two convex polyhedra in 3-space. Applications of this result to computing intersections, convex hulls, and Voronoi diagrams are given.