Number of lines tangent to four unit balls
Let $\mathcal{B}$ be a set of $n$ balls of radius $1$ in $\mathbb{R}^3$, not necessarily disjoint. Count the lines that are tangent to four balls of $\mathcal{B}$ and miss all the others; these lines dominate the complexity of the space of lines avoiding $\mathcal{B}$.
Agarwal, Aronov, Koltun and Sharir proved an upper bound of $O(n^{3+\varepsilon})$ for every $\varepsilon > 0$. The best lower bound is $\Omega(n^2)$, attained by two far-apart groups of overlapping pairs of balls, arranged so that a line tangent to one intersection circle from each group touches four balls; disjoint balls also give $\Omega(n^2)$. The number has been conjectured to be $\Omega(n^3)$; whether disjointness changes the asymptotics is not clear.
Problem. As a function of $n$, how many lines can be tangent to four balls of a set of $n$ unit balls in $\mathbb{R}^3$ while missing all the other balls?
Source: Agarwal, Aronov, Koltun and Sharir (2005); Problem 61 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- combinatorial complexity, lines tangent to balls, line transversals, The Open Problems Project
References
@article{agarwal2005,
author = {Agarwal, Pankaj K. and Aronov, Boris and Koltun, Vladlen and Sharir, Micha},
title = {Lines avoiding unit balls in three dimensions},
journal = {Discrete Comput. Geom.},
volume = {34},
year = {2005},
pages = {231--250},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01099, "Number of lines tangent to four unit balls", clopen.solutions.