Journal cover Journal topic
Geoscientific Model Development An interactive open-access journal of the European Geosciences Union
Geosci. Model Dev., 6, 1353-1365, 2013
http://www.geosci-model-dev.net/6/1353/2013/
doi:10.5194/gmd-6-1353-2013
© Author(s) 2013. This work is distributed
under the Creative Commons Attribution 3.0 License.
Model description paper
30 Aug 2013
Parallel algorithms for planar and spherical Delaunay construction with an application to centroidal Voronoi tessellations
D. W. Jacobsen1,2, M. Gunzburger1, T. Ringler2, J. Burkardt1, and J. Peterson1 1Department of Scientific Computing, Florida State University, Tallahassee, FL 32306, USA
2Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA
Abstract. A new algorithm, featuring overlapping domain decompositions, for the parallel construction of Delaunay and Voronoi tessellations is developed. Overlapping allows for the seamless stitching of the partial pieces of the global Delaunay tessellations constructed by individual processors. The algorithm is then modified, by the addition of stereographic projections, to handle the parallel construction of spherical Delaunay and Voronoi tessellations. The algorithms are then embedded into algorithms for the parallel construction of planar and spherical centroidal Voronoi tessellations that require multiple constructions of Delaunay tessellations. This combination of overlapping domain decompositions with stereographic projections provides a unique algorithm for the construction of spherical meshes that can be used in climate simulations. Computational tests are used to demonstrate the efficiency and scalability of the algorithms for spherical Delaunay and centroidal Voronoi tessellations. Compared to serial versions of the algorithm and to STRIPACK-based approaches, the new parallel algorithm results in speedups for the construction of spherical centroidal Voronoi tessellations and spherical Delaunay triangulations.

Citation: Jacobsen, D. W., Gunzburger, M., Ringler, T., Burkardt, J., and Peterson, J.: Parallel algorithms for planar and spherical Delaunay construction with an application to centroidal Voronoi tessellations, Geosci. Model Dev., 6, 1353-1365, doi:10.5194/gmd-6-1353-2013, 2013.
Publications Copernicus
Download
Share