Algorithm 872 swMATH ID: 12991 Software Authors: Chernikov, Andrey N.; Chrisochoides, Nikos Description: Algorithm 872: Parallel 2D constrained Delaunay mesh generation. 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). Homepage: http://dl.acm.org/citation.cfm?doid=1322436.1322442 Related Software: Triangle; CGAL; MSES; Algorithm 995; FUN3D; FIST; Powercrust; Cilk; TetGen; 2D triangulations; 3D triangulations; METIS; PELLPACK Cited in: 4 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Algorithm 872: Parallel 2D constrained Delaunay mesh generation. Zbl 1291.65054Chernikov, Andrey N.; Chrisochoides, Nikos 2008 all top 5 Cited by 9 Authors 2 Chernikov, Andrey N. 1 Chrisochoides, Nikos P. 1 Eder, Günther 1 Held, Martin 1 Jorquera, Gaston 1 Montenegro, Rafael 1 Palfrader, Peter 1 Pardue, Juliette 1 Rivara, Maria-Cecilia Cited in 3 Serials 2 ACM Transactions on Mathematical Software 1 Applied Numerical Mathematics 1 Computational Geometry Cited in 2 Fields 3 Numerical analysis (65-XX) 2 Computer science (68-XX) Citations by Year