# 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