נתן רובין

Let ℬ be a collection of n arbitrary balls in ℝ³. We establish an almost-tight upper bound of O(n^3+ε), for any ε > 0, on the complexity of the space ℱ(ℬ) of all the lines that avoid all the members of ℬ. In particular, we prove that the balls of ℬ admit O(n^3+ε) 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 Ω(n³) of Glisse and Lazard [6]. Our approach is constructive and yields an algorithm that computes a discrete representation of the boundary of ℱ(ℬ) in O(n^3+ε) time, for any ε > 0.