Lines Avoiding Balls in Three Dimensions Revisited

Let $\mathcal{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 $\mathcal{F}(\mathcal{B})$ of all the lines that avoid all the members of $\mathcal{B}$ . In particular, we prove that the balls of $\mathcal{B}$ admit O(n ^3+?? ) free isolated tangents, for any ??>0. This generalizes the result of Agarwal et al.?(Discrete Comput. Geom. 34:231?C250, 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?C57, 2010). Our approach is constructive and yields an algorithm that computes the discrete representation of the boundary of $\mathcal{F}(B)$ in O(n ^3+?? ) time, for any ??>0.