A compact parallel algorithm for spherical Delaunay triangulations

摘要

We present a data-parallel algorithm for the construction of Delaunay triangulations on the sphere. Ourrnmethod combines a variant of the classical Bowyer–Watson point insertion algorithm with the recently publishedrnparallelization technique by Jacobsen et al. It resolves a breakdown situation of the latter approach andrnis suitable for practical implementation because of its compact formulation. Some complementary aspectsrnare discussed such as the parallel workload and floating-point arithmetics. In a second step, the generatedrntriangulations are reordered by a stripification algorithm. This improves cache performance and significantlyrnreduces data-read operations and indirect addressing in multi-threaded stencil loops. This paper is anrnextended version of our Parallel Processing and Applied Mathematics conference contribution.