Separating a Voronoi Diagram via Local Search
Vijay Bhattiprolu, Sariel Har-Peled · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
Given a set P of n points in R^d , we show how to insert a set Z of O(n^(1-1/d)) additional points, such that P can be broken into two sets P1 and P2 , of roughly equal size, such that in the Voronoi diagram V(P u Z), the cells of P1 do not touch the cells of P2; that is, Z separates P1 from P2 in the Voronoi diagram (and also in the dual Delaunay triangulation). In addition, given such a partition (P1,P2) of P , we present an approximation algorithm to compute a minimum size separator realizing this partition. We also present a simple local search algorithm that is a PTAS for approximating the optimal Voronoi partition.