Parallel Algorithm for Spherical Delaunay Triangulations and Spherical Centroidal Voronoi Tessellations

Abstract

Spherical centroidal Voronoi tessellations (SCVT) are used in many applications in a variety of fields, one being climate modeling. They are a natural choice for spatial discretizations on the Earth, or any spherical surface. The climate modeling community, which has started to make use of SCVTs, is beginning to focus on exa-scale computing for large scale climate simulations. Due to this, a need is brought to light for fast and efficient grid generators. Current high resolution simulations on the earth call for a spatial resolution of about 11.1km. In terms of a SCVT this corresponds to a quasi-uniform SCVT with roughly 2 million Voronoi cells. Computing this grid in serial is very expensive, and can take on the order of weeks to converge sufficiently for the needs of climate modelers. Utilizing conformal mapping techniques, as well as planar triangulation algorithms, and basic domain decomposition, this paper outlines a new algorithm that can be used to compute SCVTs in parallel, thus reducing the overall time to convergence. This reduces the actual time needed to create a grid on the Earth, as well as allows for new techniques to be explored when modeling the climate.