נתן רובין

Let B 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 F(B) of all the lines that avoid all the members of B. In particular, we prove that the balls of B admit O(n ^3+ε) free isolated tangents, for any ε>0. This generalizes the result of Agarwal et al. (Discrete Comput. Geom. 34:231-250, 2005), 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 (Proc. 26th Annu. Symp. Comput. Geom., pp. 48-57, 2010). Our approach is constructive and yields an algorithm that computes the discrete representation of the boundary of F(B) in O(n ^3+ε) time, for any ε>0.