Problem 61: Lines Tangent to Four Unit Balls

Statement

Given a set of n unit-radius balls in $\mathbb {R}$³, 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 $\Omega$(n³).

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(n^3+$\epsilon$) for any $\epsilon$ > 0. The best lower bound is $\Omega$(n²), which can be achieved, for example, as follows.

Place n/4 balls separated along a horizontal line L₁, and another n/4 along a parallel line L₂ 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 L₃ and L₄, far from L₁/L₂ 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 L₁/L₂ group, one from the L₃/L₄ group, is tangent to four balls. And there are $\Omega$(n²) 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.