
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.