Separating a Voronoi Diagram via Local Search

Abstract

Given a set $\mathsf{P}$ of $n$ points in ${\mathbb{R}}^d$, we show how to insert a set $\mathsf{X}$ of $O(n^{1-1/d})$ additional points, such that $\mathsf{P}$ can be broken into two sets ${\mathsf{P}}_1$ and ${\mathsf{P}}_2$, of roughly equal size, such that in the Voronoi diagram $\mathcal{V}(\mathsf{P}\cup \mathsf{X})$, the cells of ${\mathsf{P}}_1$ do not touch the cells of ${\mathsf{P}}_2$; that is, $\mathsf{X}$ separates ${\mathsf{P}}_1$ from ${\mathsf{P}}_2$ in the Voronoi diagram. Given such a partition $({\mathsf{P}}_1,{\mathsf{P}}_2)$ of $\mathsf{P}$, we present approximation algorithms to compute the minimum size separator realizing this partition. Finally, we present a simple local search algorithm that is a PTAS for geometric hitting set of fat objects (which can also be used to approximate the optimal Voronoi partition).