Halving Balls in Deterministic Linear Time

Let ${\mathcal{D}}$ be a set of n pairwise disjoint unit balls in ℝ d and P the set of their center points. A hyperplane ${\mathcal{H}}$ is an m-separator for ${\mathcal{D}}$ if each closed halfspace bounded by ${\mathcal{H}}$ contains at least m points from P. This generalizes the notion of halving hyperplanes (n/2-separators). The analogous notion for point sets has been well studied. Separators have various applications, for instance, in divide-and-conquer schemes. In such a scheme any ball that is intersected by the separating hyperplane may still interact with both sides of the partition. Therefore it is desirable that the separating hyperplane intersects a small number of balls only.