Lines avoiding balls in three dimensions revisited
Natan Rubin · 2010
Let B be a collection of n arbitrary balls in ℜ3. We establish an almost-tight upper bound of O(n3+ε), for any ε > 0, on the complexity of the space F(B) of all the lines that avoid all the members of B. In particular, we prove that the balls of B admit O(n3+ε) free isolated tangents, for any ε > 0. This generalizes the result of Agarwal et al. [1], who established this bound only for congruent balls, and solves an open problem posed in that paper. Our bound almost meets the recent lower bound of Ω(n3) of Glisse and Lazard [6].