Finding stabbing lines in 3-space

A line intersecting all polyhedra in a setℬ is called a “stabber” for the setℬ. This paper addresses some combinatorial and algorithmic questions about the setℒ(ℬ) of all lines stabbingℬ. We prove that the combinatorial complexity ofℒ(ℬ) has an upper bound, wheren is the total number of facets inℬ, andc is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one. The research of M. Pellegrini was partially supported by Eni and Enidata within the AXL project, and by NSF Grant CCR-8901484. A preliminary version appeared in theProceedings of the Second ACM-SIAM Symposium on Discrete Algorithms, pp. 24–31.