Polyhedral line transversals in space |
| |
Authors: | David Avis Rephael Wenger |
| |
Institution: | (1) School of Computer Science, McGill University, 805 Sherbrooke Street W., H3A 2K6 Montreal, Canada |
| |
Abstract: | Algorithms are developed for determining if a set of polyhedral objects inR
3 can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n
4 logn) 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|