Localizing the Delaunay triangulation and its parallel implementation

Renjie Chen, Craig Gotsman

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
Pages24-31
Number of pages8
DOIs
StatePublished - 2012
Externally publishedYes
Event2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 - Piscataway, NJ, United States
Duration: Jun 27 2012Jun 29 2012

Publication series

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

Other

Other2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
CountryUnited States
CityPiscataway, NJ
Period6/27/126/29/12

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Localizing the Delaunay triangulation and its parallel implementation'. Together they form a unique fingerprint.

Cite this