Stabbing triangulations by lines in 3D
Published
Conference Paper
© 1995 ACM. Let S be a set of (possibly degenerate) triangles in R3 whose interiors are disjoint. A triangulation of R3 with respect to S, denoted by T(S), is a simplicial complex in which each face of T(S) is either disjoint from S or contained in a higher dimensional face of S. The line stabbing number of T(S) is the maximum number of tetrahedra of T(S) intersected by a segment that does not intersect any triangle of S. We investigate the line stabbing number of triangulations in several cases-when S is a set of points, when the triangles of 5 form the boundary of a convex or a nonconvex polyhedron, or when the triangles of S form the boundaries of k disjoint convex polyhedra. We prove almost tight worst-case upper and lower bounds on line stabbing numbers for these cases. We also estimate the number of tetrahedra necessary to guarantee low stabbing number.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Aronov, B; Suri, S
Published Date
- September 1, 1995
Published In
- Proceedings of the Annual Symposium on Computational Geometry
Volume / Issue
- Part F129372 /
Start / End Page
- 267 - 276
International Standard Book Number 10 (ISBN-10)
- 0897917243
Digital Object Identifier (DOI)
- 10.1145/220279.220308
Citation Source
- Scopus