Separating a voronoi diagram via local search

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

doi:10.4230/LIPIcs.SoCG.2016.18

Separating a voronoi diagram via local search

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

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a set P of n points in ℝ^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 P₁ and P₂, of roughly equal size, such that in the Voronoi diagram V(P ∪ Z), the cells of P₁ do not touch the cells of P₂; that is, Z separates P₁ from P₂ in the Voronoi diagram (and also in the dual Delaunay triangulation). In addition, given such a partition (P₁, P₂) 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 language	English (US)
Title of host publication	32nd International Symposium on Computational Geometry, SoCG 2016
Editors	Sandor Fekete, Anna Lubiw
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	18.1-18.16
ISBN (Electronic)	9783959770095
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2016.18
State	Published - Jun 1 2016
Event	32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States Duration: Jun 14 2016 → Jun 17 2016

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	51
ISSN (Print)	1868-8969

Other

Other	32nd International Symposium on Computational Geometry, SoCG 2016
Country/Territory	United States
City	Boston
Period	6/14/16 → 6/17/16

Keywords

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

ASJC Scopus subject areas

Software

Online availability

10.4230/LIPIcs.SoCG.2016.18

Library availability

Discover UIUC Full Text

Cite this

Bhattiprolu, V. V. S. P., & Har-Peled, S. (2016). Separating a voronoi diagram via local search. In S. Fekete, & A. Lubiw (Eds.), 32nd International Symposium on Computational Geometry, SoCG 2016 (pp. 18.1-18.16). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 51). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.18

Separating a voronoi diagram via local search. / Bhattiprolu, Vijay V.S.P.; Har-Peled, Sariel.
32nd International Symposium on Computational Geometry, SoCG 2016. ed. / Sandor Fekete; Anna Lubiw. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. p. 18.1-18.16 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 51).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bhattiprolu, VVSP & Har-Peled, S 2016, Separating a voronoi diagram via local search. in S Fekete & A Lubiw (eds), 32nd International Symposium on Computational Geometry, SoCG 2016. Leibniz International Proceedings in Informatics, LIPIcs, vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 18.1-18.16, 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, United States, 6/14/16. https://doi.org/10.4230/LIPIcs.SoCG.2016.18

@inproceedings{48066638868e4817b93bc80c597dd8ca,

title = "Separating a voronoi diagram via local search",

abstract = "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.",

keywords = "Approximation, Delaunay triangulation, Geometric hitting set, Local search, Meshing, Separators, Voronoi diagrams",

author = "Bhattiprolu, {Vijay V.S.P.} and Sariel Har-Peled",

note = "Publisher Copyright: {\textcopyright} Vijay V. S. P. Bhattiprolu and Sariel Har-Peled.; 32nd International Symposium on Computational Geometry, SoCG 2016 ; Conference date: 14-06-2016 Through 17-06-2016",

year = "2016",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2016.18",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "18.1--18.16",

editor = "Sandor Fekete and Anna Lubiw",

booktitle = "32nd International Symposium on Computational Geometry, SoCG 2016",

}

TY - GEN

T1 - Separating a voronoi diagram via local search

AU - Bhattiprolu, Vijay V.S.P.

AU - Har-Peled, Sariel

N1 - Publisher Copyright: © Vijay V. S. P. Bhattiprolu and Sariel Har-Peled.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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.

AB - 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.

KW - Approximation

KW - Delaunay triangulation

KW - Geometric hitting set

KW - Local search

KW - Meshing

KW - Separators

KW - Voronoi diagrams

UR - http://www.scopus.com/inward/record.url?scp=84976863851&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976863851&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2016.18

DO - 10.4230/LIPIcs.SoCG.2016.18

M3 - Conference contribution

AN - SCOPUS:84976863851

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 18.1-18.16

BT - 32nd International Symposium on Computational Geometry, SoCG 2016

A2 - Fekete, Sandor

A2 - Lubiw, Anna

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd International Symposium on Computational Geometry, SoCG 2016

Y2 - 14 June 2016 through 17 June 2016

ER -

Separating a voronoi diagram via local search

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this