Algorithm 872: Parallel 2D Constrained Delaunay Mesh Generation. Andrey Chernikov and Nikos Chrisochoides. ACM Transactions on Mathematical Software (Vol. 34, No. 1, pp. 6-25), January 2008.

Abstract

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).

Paper draft

pdf format pdf (842 K)

BibTex

@article{toms06,
    author = "Andrey Chernikov and Nikos Chrisochoides",
    title = "Algorithm 872: Parallel 2D Constrained Delaunay Mesh Generation",
    journal = "ACM Transactions on Mathematical Software",
    year = "2008",
    month = "January",
    volume = "34",
    issue = "1",
    pages = "6--25",
}