On the complexity of sets of free lines and line segments among balls in three dimensions

DOI10.1007/S00454-012-9414-8MaRDI QIDQ420577zbMATHOpenAlexFDO

Authors Marc Glisse, Sylvain Lazard

Publication date 22 May 2012

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-012-9414-8

zbMATH Keywords

balls3D visibilityfree linesfree segmentsvisibility complex

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Recommendations

• On the complexity of sets of free lines and line segments among balls in three dimensions
• Lines avoiding balls in three dimensions revisited
• Lines avoiding balls in three dimensions revisited
• On lines avoiding unit balls in three dimensions
• Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
• Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra
• On nearly free arrangements of lines with nodes and triple points
• Maximum line-free set geometry in \(\mathbb Z^d_3\)
• Combinatorial complexity bounds for arrangements of curves and spheres
• An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$

Cites work

• Common tangents to four unit balls in \(\mathbb{R}^3\)
• Common tangents to spheres in \(\mathbb R^{3}\)
• Common transversals and tangents to two lines and two quadrics in \(P\)
• Line transversals of balls and smallest enclosing cylinders in three dimensions
• Line transversals of convex polyhedra in \(\mathbb{R}^3\)
• Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra
• Lines avoiding balls in three dimensions revisited
• Lines avoiding unit balls in three dimensions
• Lines in space: Combinatorics and algorithms
• Lines tangent to four triangles in three-dimensional space
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• On incremental rendering of silhouette maps of a polyhedral scene
• On lines missing polyhedral sets in 3-space
• On the complexity of umbra and penumbra
• THE VISIBILITY COMPLEX
• The Expected Number of 3D Visibility Events Is Linear
• The envelope of lines meeting a fixed line and tangent to two spheres
• The union of moving polygonal pseudodiscs -- combinatorial bounds and applications
• Transversals to line segments in three-dimensional space

Cited in

(7)

• On lines avoiding unit balls in three dimensions
• Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra
• On the complexity of sets of free lines and line segments among balls in three dimensions
• Lines avoiding balls in three dimensions revisited
• Lines avoiding balls in three dimensions revisited
• Lines avoiding unit balls in three dimensions
• Pipes, cigars, and Kreplach: The union of Minkowski sums in three dimensions

This page was built for publication: On the complexity of sets of free lines and line segments among balls in three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q420577)