Space sweep solves intersection of two convex polyhedra elegantly

Abstract

Plane-sweep algorithms form a fairly general approach to two-dimensional problems of computational geometry. No corresponding three-dimensional space-sweep algorithms for geometric problems in 3-space are known, however. We derive concepts for such space-sweep algorithms that yield an elegant solution to the problem of solving any set operation (union, intersection, ...) of two convex polyhedra. Moreover, our solution matches the best known time bound of O(n log n) where n is the combined number of corners of the two polyhedra.