Halving balls by a hyperplane in deterministic linear time
Michael M. Hoffmann, Vincent J. J. Kusters, Tillmann Miltzow · Journal of Computational Geometry (Carleton University) · 2018
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