Localizing the Delaunay triangulation and its parallel implementation

Renjie Chen; Craig Gotsman

doi:10.1109/ISVD.2012.9

Localizing the Delaunay triangulation and its parallel implementation

Renjie Chen, Craig Gotsman

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

7 Scopus citations

Abstract

We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines.

Original language	English (US)
Title of host publication	Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
Pages	24-31
Number of pages	8
DOIs	https://doi.org/10.1109/ISVD.2012.9
State	Published - 2012
Externally published	Yes
Event	2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 - Piscataway, NJ, United States Duration: Jun 27 2012 → Jun 29 2012

Publication series

Name	Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

Other

Other	2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
Country/Territory	United States
City	Piscataway, NJ
Period	6/27/12 → 6/29/12

All Science Journal Classification (ASJC) codes

Geometry and Topology

Access to Document

10.1109/ISVD.2012.9

Cite this

Chen, R., & Gotsman, C. (2012). Localizing the Delaunay triangulation and its parallel implementation. In Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 (pp. 24-31). Article 6257653 (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012). https://doi.org/10.1109/ISVD.2012.9

@inproceedings{1bea2633850a4adc99355a4579e9618e,

title = "Localizing the Delaunay triangulation and its parallel implementation",

abstract = "We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines.",

author = "Renjie Chen and Craig Gotsman",

year = "2012",

doi = "10.1109/ISVD.2012.9",

language = "English (US)",

isbn = "9780769547244",

series = "Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012",

pages = "24--31",

booktitle = "Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012",

note = "2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 ; Conference date: 27-06-2012 Through 29-06-2012",

}

Chen, R & Gotsman, C 2012, Localizing the Delaunay triangulation and its parallel implementation. in Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012., 6257653, Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012, pp. 24-31, 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012, Piscataway, NJ, United States, 6/27/12. https://doi.org/10.1109/ISVD.2012.9

Localizing the Delaunay triangulation and its parallel implementation. / Chen, Renjie; Gotsman, Craig.
Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012. 2012. p. 24-31 6257653 (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012).

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

TY - GEN

T1 - Localizing the Delaunay triangulation and its parallel implementation

AU - Chen, Renjie

AU - Gotsman, Craig

PY - 2012

Y1 - 2012

N2 - We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines.

AB - We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines.

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

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

U2 - 10.1109/ISVD.2012.9

DO - 10.1109/ISVD.2012.9

M3 - Conference contribution

AN - SCOPUS:84866786537

SN - 9780769547244

T3 - Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

SP - 24

EP - 31

BT - Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

T2 - 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

Y2 - 27 June 2012 through 29 June 2012

ER -

Localizing the Delaunay triangulation and its parallel implementation

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this