A compact parallel algorithm for spherical Delaunay triangulations. (5th October 2016) - Prill, Florian; Zängl, Günther
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.