Halving balls by a hyperplane in deterministic linear time

Abstract

Let D be a set of n pairwise disjoint unit balls in R-d and P the set of their centers. A hyperplane H is an m-separator for D if every 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 is 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.

We present three deterministic algorithms to bisect a given set of pairwise disjoint unit balls by a hyperplane. Firstly, we present a simple linear-time algorithm to construct an alpha n-separator for balls in R-d, for any 0 < alpha < 1/2, that intersects at most cn((d-1)/d) balls, for some constant c that depends on d and alpha. 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. Finally, we give a linear-time algorithm to construct a halving line in R-2 for P that intersects O(n((2=3)+epsilon)) disks.

We also point out how the above theorems can be generalized to more general classes of shapes, possibly with some overlap, and what are the limits of those generalizations. Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results simplify and derandomize an algorithm to construct a space decomposition used by Loffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk).