Publication Details




Algorithm 872: Parallel 2D Constrained Delaunay Mesh Generation


Andrey Chernikov and Nikos Chrisochoides.


Published in ACM Transactions on Mathematical Software, Volume 34, No. 1, pages 6 -- 25, January, 2008




Delaunay refinement is a widely used method for the construction of guaranteed quality triangular and tetrahedral meshes. We present an algorithm and a software for the parallel constrained Delaunay mesh generation in two dimensions. Our approach is based on the decomposition of the original mesh generation problem into N smaller subproblems which are meshed in parallel. The parallel algorithm is asynchronous with small messages which can be aggregated and exhibits low communication costs. On a heterogeneous cluster of more than 100 processors our implementation can generate over one billion triangles in less than 3 minutes, while the single-node performance is comparable to that of the fastest to our knowledge sequential guaranteed quality Delaunay meshing library (the Triangle).




  [PDF]          [BibTex] 



[Return to Publication List]