High-Performance Computation of Distributed-Memory Parallel 3D Voronoi and Delaunay Tessellation
Authors:
- Tom PeterkaTPTom Peterka
- Dmitriy MorozovDMDmitriy Morozov
- Carolyn PhillipsCPCarolyn Phillips
- 1 November 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21674329,p. 997-1007
Abstract
Computing a Voronoi or Delaunay tessellation from a set of points is a core part of the analysis of many simulated and measured datasets: N-body simulations, molecular dynamics codes, and LIDAR point clouds are just a few examples. Such computational geometry methods are common in data analysis and visualization, but as the scale of simulations and observations surpasses billions of particles, the existing serial and shared memory algorithms no longer suffice. A distributed-memory scalable parallel algorithm is the only feasible approach. The primary contribution of this paper is a new parallel Delaunay and Voronoi tessellation algorithm that automatically determines which neighbor points need to be exchanged among the sub domains of a spatial decomposition. Other contributions include periodic and wall boundary conditions, comparison of our method using two popular serial libraries, and application to numerous science datasets.Keywords
This publication has 32 references indexed in Scilit:
- Nyx: A MASSIVELY PARALLEL AMR CODE FOR COMPUTATIONAL COSMOLOGYThe Astrophysical Journal, 2013
- Stability of the double gyroid phase to nanoparticle polydispersity in polymer-tethered nanosphere systemsSoft Matter, 2010
- Hybrid petacomputing meets cosmology: The Roadrunner Universe projectJournal of Physics: Conference Series, 2009
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996
- Incremental topological flipping works for regular triangulationsAlgorithmica, 1996
- Designing the computational geometry algorithms library CGAL1996
- Parallel 3D Delaunay TriangulationComputer Graphics Forum, 1993
- Randomized incremental construction of Delaunay and Voronoi diagramsAlgorithmica, 1992
- An improved parallel algorithm for constructing voronoi diagram on a mesh-connected computerParallel Computing, 1991
- Efficient parallel convex hull algorithmsIEEE Transactions on Computers, 1988