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

DOI10.1007/S00454-012-9414-8zbMATH Open1242.52029OpenAlexW4242713488MaRDI QIDQ420577FDOQ420577

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

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$

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)

Cites Work

• The envelope of lines meeting a fixed line and tangent to two spheres
• Common tangents to spheres in \(\mathbb R^{3}\)
• Common tangents to four unit balls in \(\mathbb{R}^3\)
• On the complexity of umbra and penumbra
• The union of moving polygonal pseudodiscs -- combinatorial bounds and applications
• Line transversals of balls and smallest enclosing cylinders in three dimensions
• On lines missing polyhedral sets in 3-space
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• Common transversals and tangents to two lines and two quadrics in \(P\)
• Lines in space: Combinatorics and algorithms
• On incremental rendering of silhouette maps of a polyhedral scene
• Lines avoiding unit balls in three dimensions
• Transversals to line segments in three-dimensional space
• The Expected Number of 3D Visibility Events Is Linear
• 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
• THE VISIBILITY COMPLEX
• Lines tangent to four triangles 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
• Pipes, cigars, and Kreplach: The union of Minkowski sums in three dimensions
• Lines avoiding unit balls 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)