ALGORITHMS FOR HIGH DIMENSIONAL STABBING PROBLEMS

Given a set of geometric objects in Rd, the hyperplane transversal or stabbing problem is to determine if there exists a hyperplane that simultaneously intersects all of the objects. We give algorithms based on linear programming for various hyperplane stabbing problems where the objects are line segments or convex polyhedra. A hyperplane stabber for n segments in Rd can be found in O(nd) time. In Rd, a plane stabber for a set of m polyhedra with a total of n edges can be found in O(nd-1m) time and space. Given a query hyperplane, a list of polyhedra intersected by the hyperplane can be determined in O(logn+m) time. © 1990.