ON STABBING LINES FOR CONVEX POLYHEDRA IN 3D

A line l is called a stabbing line for a set B of convex polyhedra in R3 if it intersects every polyhedron of B. This paper presents an upper bound of O(n3 log n) on the complexity of the space of stabbing lines for B, where n is the number of edges in the polyhedra of B. We solve a more general problem that counts the number of faces in a set of convex polyhedra, which are implicitly defined by a set of half-spaces and a set of hyperplanes. We show that the former problem is a special case of the latter problem. We also apply this technique to obtain an upper bound on the number of distinct faces that ever appear on the intersection of a set of half-spaces as we insert or delete half-spaces dynamically.