Sparse parallel Delaunay mesh refinement

Citations Over TimeTop 10% of 2007 papers

Abstract

The authors recently introduced the technique of sparse mesh refinement to produce the first near-optimal sequential time bounds of O(n lg L/s+m) for inputs in any fixed dimension with piecewiselinear constraining (PLC) features. This paper extends that work to the parallel case, refining the same inputs in time O(lg(L/s) lgm) on an EREW PRAM while maintaining the work bound; in practice, this means we expect linear speedup for any practical number of processors. This is faster than the best previously known parallel Delaunay mesh refinement algorithms in two dimensions. It is the first technique with work bounds equal to the sequential case. In higher dimension, it is the first provably fast parallel technique for any kind of quality mesh refinement with PLC inputs. Furthermore, the algorithm's implementation is straightforward enough that it is likely to be extremely fast in practice.

Related Papers

• → 3D Delaunay mesh generation coupled with an advancing-front approach(1998)100 cited
• → A frontal approach for internal node generation in Delaunay triangulations(1993)74 cited
• → Dynamic Parallel 3D Delaunay Triangulation(2011)22 cited
• → Three-Dimensional finite element mesh generation using delaunay tesselation(1985)74 cited
• → Automatic Mesh Generation by Delaunay Triangulation and Its Application to Remeshing(1996)