Name
Abstract | ||
|---|---|---|
Algorithms are developed for determining if a set of polyhedral objects inR3 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(n4 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. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/BF02187911 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Line Segment,Projective Space,Discrete Comput Geom,Computational Geometry,Quadric Surface | Discrete mathematics,Line segment,Combinatorics,Vertex (geometry),Polyhedron,Computational geometry,Transversal (geometry),Quadric,Mathematics,Projective space | Journal |
Volume | Issue | ISSN |
3 | 3 | 0179-5376 |
Citations | PageRank | References |
10 | 1.29 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Avis | 1 | 10 | 1.29 |
| Rephael Wenger | 2 | 441 | 43.54 |