Algorithms for line transversals in space
David Avis, Rephael Wenger · 1987
Algorithms are developed for determining if a set of polyhedral objects in R3 can be intersected by a common transversal (stabbing) line. It can be determined in Ο(n) time if a set of n lines in space has a line transversal, and such a transversal can be found in the same time bound. For a set of n line segments, the complexity of finding such a transversal becomes Ο(nlogn). Finally, for a set of polyhedra with a total of n vertices, we give a Ο(n5) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.