Stabbing triangulations by lines in 3D

Pankaj K. Agarwal; Boris Aronov; Subhash Suri

doi:10.1145/220279.220308

Stabbing triangulations by lines in 3D

Pankaj K. Agarwal, Boris Aronov, Subhash Suri

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let S be a set of (possibly degenerate) triangles in R³ whose interiors are disjoint. A triangulation of R³ 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	https://doi.org/10.1145/220279.220308
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

Access to Document

10.1145/220279.220308

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

Cite this

Stabbing triangulations by lines in 3D. / Agarwal, Pankaj K.; Aronov, Boris; Suri, Subhash.

Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995. Association for Computing Machinery, 1995. p. 267-276 (Proceedings of the Annual Symposium on Computational Geometry; Vol. Part F129372).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Agarwal, PK, Aronov, B & Suri, S 1995, Stabbing triangulations by lines in 3D. in Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995. Proceedings of the Annual Symposium on Computational Geometry, vol. Part F129372, Association for Computing Machinery, pp. 267-276, 11th Annual Symposium on Computational Geometry, SCG 1995, Vancouver, Canada, 6/5/95. https://doi.org/10.1145/220279.220308

@inproceedings{748c81318d3145bfba791cdb57c7d72a,

title = "Stabbing triangulations by lines in 3D",

abstract = "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.",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Subhash Suri",

note = "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.; 11th Annual Symposium on Computational Geometry, SCG 1995 ; Conference date: 05-06-1995 Through 07-06-1995",

year = "1995",

month = sep,

day = "1",

doi = "10.1145/220279.220308",

language = "English (US)",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery",

pages = "267--276",

booktitle = "Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995",

}

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.

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 -