Biological and Environmental Research - Earth and Environmental System Sciences
Earth and Environmental System Modeling
25 April 2014

Parallel Algorithms for Planar and Spherical Delaunay Construction with an Application to Centroidal Voronoi Tessellations


Significant computational resources are required when using traditional techniques for the creation of spherical centroidal Voronoi tessellations. These meshes can employ a density function that allows the creation of variable resolution spherical meshes for use in various climate models. DOE researches developed a new algorithm, featuring overlapping domain decompositions, for the parallel construction of Delaunay and Voronoi tessellations. The algorithm is then modified to employ a stereographic projection the allows parallel construction of spherical Delaunay and Voronoi tessellations. Compared to traditional approaches, this new algorithm results in significant speedups for the construction of quasi-uniform and variable resolution spherical meshes for use in new DOE climate model components.