Premium
A compact parallel algorithm for spherical Delaunay triangulations
Author(s) -
Prill Florian,
Zängl Günther
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3971
Subject(s) - stencil , delaunay triangulation , parallel computing , computer science , ruppert's algorithm , chew's second algorithm , algorithm , point (geometry) , bowyer–watson algorithm , parallel algorithm , mathematics , computational science , geometry
Summary We present a data‐parallel algorithm for the construction of Delaunay triangulations on the sphere. Our method combines a variant of the classical Bowyer–Watson point insertion algorithm with the recently published parallelization technique by Jacobsen et al . It resolves a breakdown situation of the latter approach and is suitable for practical implementation because of its compact formulation. Some complementary aspects are discussed such as the parallel workload and floating‐point arithmetics. In a second step, the generated triangulations are reordered by a stripification algorithm. This improves cache performance and significantly reduces data‐read operations and indirect addressing in multi‐threaded stencil loops. This paper is an extended version of our Parallel Processing and Applied Mathematics conference contribution. Copyright © 2016 John Wiley & Sons, Ltd.