An optimal algorithm for intersecting three-dimensional convex polyhedra

A linear algorithm for intersecting two convex polyhedra in 3-space is described. The algorithm is quite simple; it does not require any complicated data structure and should be practical. A number of optimal algorithms for other problems are obtained directly from this result. These include intersecting several polytopes at once or computing the convex hull of their union, merging Voronoi diagrams in the plane in linear time, and computing three-dimensional convex hulls in linear expected time.>