Stabbing triangulations by lines in 3D

Pankaj K. Agarwal, Boris Aronov, Subhash Suri

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995
    PublisherAssociation for Computing Machinery
    Number of pages10
    ISBN (Electronic)0897917243
    StatePublished - Sep 1 1995
    Event11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, Canada
    Duration: Jun 5 1995Jun 7 1995

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry
    VolumePart F129372


    Other11th Annual Symposium on Computational Geometry, SCG 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics


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

    Cite this