Home Bookmarks Papers Blog

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.
Last modified: Sun Apr 13 10:45:40 CDT 2014