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 -