An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$
Thorsten Theobald · SIAM Journal on Computing · 2002
We investigate the enumerative geometry aspects of algorithmic line problems when the admissible bodies are balls or polytopes. For this purpose, we study the common tangent lines/transversals to k balls of arbitrary radii and 4-k lines in ${\mathbb R}^3$. In particular, we compute tight upper bounds for the maximum number of real common tangents/transversals in these cases. Our results extend the results of Macdonald, Pach, and Theobald who investigated common tangents to four unit balls in ${\mathbb R}^3$ [Discrete Comput. Geom., 26 (2001), pp. 1--17].