A dual approach to detect polyhedral intersections in arbitrary dimensions (Q758179)

The authors consider convex polyhedra with n vertices in d-dimensional space. They present algorithms to detect intersections of hyperplanes and convex polyhedra as well as polyhedron-polyhedron intersections. (``detection'' means to establish whether or not the intersections are nonvoid). The complexities are \(O(2^ d \log n)\) and \(O((2d)^{d- 1}\log^{d-1}n)\) respectively. However, the space and preprocessing requirements are \(O(n^{2^ d})\) for general d. The paper contains a survey of previous results and some suggestions for future work.