Parallel Algorithm for Spherical Delaunay Triangulations and Spherical Centroidal Voronoi

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. As the data size increases, the efficiency of the grid generator becomes extremely important. Current high resolution simulations on the earth call for a spatial resolution of about 15km. In terms of an SCVT this corresponds to a quasi-uniform SCVT with roughly 2 million Voronoi cells. Computing this grid serially is very expensive and can take on the order of weeks to converge sufficiently for the needs of climate modelers. This paper outlines a new algorithm that utilizes existing computational geometry tools such as conformal mapping techniques, planar triangulation algorithms, and basic domain decomposition, to compute SCVTs in parallel, thus reducing the overall time to convergence. This new algorithm shows speedup on the order of 4000 when using 42 processors over STRIPACK in computing a triangulation used for generating an SCVT