### Abstract

Let S be a set of (possibly degenerate) triangles in R^{3} whose interiors are disjoint. A triangulation of R^{3} 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995 |

Publisher | Association for Computing Machinery |

Pages | 267-276 |

Number of pages | 10 |

ISBN (Electronic) | 0897917243 |

DOIs | |

State | Published - Sep 1 1995 |

Event | 11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, Canada Duration: Jun 5 1995 → Jun 7 1995 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|---|

Volume | Part F129372 |

### Other

Other | 11th Annual Symposium on Computational Geometry, SCG 1995 |
---|---|

Country | Canada |

City | Vancouver |

Period | 6/5/95 → 6/7/95 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Stabbing triangulations by lines in 3D'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995*(pp. 267-276). (Proceedings of the Annual Symposium on Computational Geometry; Vol. Part F129372). Association for Computing Machinery. https://doi.org/10.1145/220279.220308