Summary. Plane-sweep algorithms form a fairly general approach to twodimensional problems of computational geometry. No corresponding general space-sweep algorithms for geometric problems in 3-space are known. We derive concepts for such space-sweep algorithms that yield an efficient solution to the problem of solving any set operation (union, intersection .... ) of two convex polyhedra. Our solution matches the best known time bound of O(n log n), where n is the combined number of vertices of the two polyhedra.
For example, in REF the time complexity of O(n log n) is achieved for computing the intersection of two convex polyhedra if their surfaces are pre-triangulated.
Space sweep solves intersection of convex polyhedra
Acta Informatica
Acta Informatica
Computer Science Mathematics