Separating a Voronoi Diagram via Local Search
$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}$
Sariel Har-Peled,
and
Vijay V. S. P. Bhattiprolu.
Given a set $P$ of $n$ points in $\Re^d$, we show how to
insert a set $\SetX$ of $O\big( n^{1-1/d} )$ additional points,
such that $P$ can be broken into two sets $P_1$ and
$P_2$, of roughly equal size, such that in the Voronoi
diagram $\VorX{P \cup \SetX}$, the cells of $P_1$ do
not touch the cells of $P_2$; that is, $\SetX$ separates
$P_1$ from $P_2$ in the Voronoi diagram.
Given such a partition $(P_1,P_2)$ of $P$, we
present approximation algorithms to compute the minimum size
separator realizing this partition.
PDF.
Last modified: Sun Apr 13 10:45:40 CDT 2014