zbMATH — the first resource for mathematics

Localizing the Delaunay triangulation and its parallel implementation. (English) Zbl 1406.68114
Gavrilova, Marina L. (ed.) et al., Transactions on Computational Science XX. Special issue on Voronoi diagrams and their applications. Berlin: Springer (ISBN 978-3-642-41904-1/pbk). Lecture Notes in Computer Science 8110. Journal Subline, 39-55 (2013).
Summary: 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.
For the entire collection see [Zbl 1277.68011].

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W10 Parallel algorithms in computer science
Full Text: DOI