Separating Balls with a Hyperplane
Michael Homann, Vincent J. J. Kusters, Tillmann Miltzow · 2014
LetD be a set of n pairwise disjoint unit balls in R d and P the set of their center points. A hyperplane H is an m-separator for D if each closed halfspace bounded by H contains at least m points from P. This generalizes the notion of halving hyperplanes, which correspond to n=2-separators. The analogous notion for point sets has been well studied. Separators have various applications, for instance, in divide-andconquer 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. We present two deterministic algorithms to bisect or approximately bisect a given set of disjoint unit balls by a hyperplane: Firstly, we present a simple linear-time algorithm to construct ann -separator for balls in R d , for any 0 < < 1=2, that intersects at mostcn (d 1)=d balls, for some constantc that depends on d and . The number of intersected balls is best possible up to the constant c. Secondly, we present a near-linear time algorithm to construct an (n=2 o(n))-separator in R d that intersects o(n) balls.