TY - GEN
T1 - Stabbing triangulations by lines in 3D
AU - Agarwal, Pankaj K.
AU - Aronov, Boris
AU - Suri, Subhash
N1 - Funding Information:
*The work by the first author was supported by National Science Foundation Grant Grant CC R-93–Ol 259, an NYI award, and by matching funds from Xerox Corp. The work by the second author was supported by National Science Foundation Grant CCR-92-11541.
Publisher Copyright:
© 1995 ACM.
PY - 1995/9/1
Y1 - 1995/9/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0040172907&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0040172907&partnerID=8YFLogxK
U2 - 10.1145/220279.220308
DO - 10.1145/220279.220308
M3 - Conference contribution
AN - SCOPUS:0040172907
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 267
EP - 276
BT - Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995
PB - Association for Computing Machinery
T2 - 11th Annual Symposium on Computational Geometry, SCG 1995
Y2 - 5 June 1995 through 7 June 1995
ER -