| ALGORITHMS FOR LINE TRANSVERSALS IN SPACE Preliminary Report (2008) | |||||||||||||
Abstract | |||||||||||||
| Algorithms are developed for determining if a set of polyhedral objects in R 3 can be intersected by a common transversal (stabbing) line. It can be determined in O(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 aset of n line segments, the complexity of finding such a transversal becomes O(nlogn). Finally, for a set of polyhedra with a total of n vertices, we give a O(n 5)algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, itisshown 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. 1. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||