Separating a voronoi diagram via local search

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given a set P of n points in ℝd, we show how to insert a set Z of O(n1-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 ∪ 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.

Original languageEnglish (US)
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
EditorsSandor Fekete, Anna Lubiw
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770095
StatePublished - Jun 1 2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: Jun 14 2016Jun 17 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other32nd International Symposium on Computational Geometry, SoCG 2016
Country/TerritoryUnited States


  • Approximation
  • Delaunay triangulation
  • Geometric hitting set
  • Local search
  • Meshing
  • Separators
  • Voronoi diagrams

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Separating a voronoi diagram via local search'. Together they form a unique fingerprint.

Cite this