Stabbing triangulations by lines in 3D


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