Separating a Voronoi Diagram via Local Search

Vijay V. S. P. Bhattiprolu, Sariel Har-Peled

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…