next up previous
Next: Problem 62: Volume Maximizing Up: The Open Problems Project Previous: Problem 60: Transforming Polygons


Problem 61: Lines Tangent to Four Unit Balls

Statement
Given a set of n unit-radius balls in $ \mathbb {R}$3, what is the number of lines that are tangent to four of the balls in the set, and miss all the others? (The balls are not necessarily disjoint.)
Origin
[AAKS05].
Status/Conjectures
Open, conjectured to be Ω(n3).
Motivation
The number of lines tangent to four unit balls dominates the combinatorial complexity of the space of lines that avoid all the balls. And this complexity is related to questions in visibility and in optimization.
Partial and Related Results
In [AAKS05] it is established that the number is O(n3+ε) for any ε > 0. The best lower bound is Ω(n2), which can be achieved, for example, as follows.

Place n/4 balls separated along a horizontal line L1, and another n/4 along a parallel line L2 below, with each of the lower balls directly below an upper ball with their centers 1 unit apart. Thus each pair of balls overlap, their surfaces intersecting in a circle. Arrange a second set of n/4 pairs of intersecting balls along lines L3 and L4, far from L1/L2 and with all four lines parallel, and such that all circles of sphere intersections are coplanar. Now it is easy to see that a line tangent to two circles of intersection, one from the L1/L2 group, one from the L3/L4 group, is tangent to four balls. And there are Ω(n2) such lines. (The same bound can be achieved with disjoint balls with a similar arrangement, but the analysis is slight more complex.)

The problem is also interesting if all balls are disjoint; it is not clear if disjointness affects the answer asymptotically.

Appearances
[AAKS05].
Categories
combinatorial geometry
Entry Revision History
J. O'Rourke, 25 Aug. 2005.

Bibliography

AAKS05
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, and Micha Sharir.
Lines avoiding unit balls in three dimensions.
Discrete Comput. Geom., 34:231-250, 2005.


next up previous
Next: Problem 62: Volume Maximizing Up: The Open Problems Project Previous: Problem 60: Transforming Polygons
The Open Problems Project - December 04, 2015