Boundary Refinement in Delaunay Mesh Generation Using Arbitrarily Ordered Vertex Insertion.
Démian Nave, Nikos P. Chrisochoides · Canadian Conference on Computational Geometry · 2005
In general, guaranteed-quality Delaunay meshing algorithms are difficult to parallelize because they require strictly ordered updates to the mesh boundary. We show that, by replacing the Delaunay cavity in the Bowyer-Watson algorithm with what we call the circumball intersection set, updates to the mesh can occur in any order, especially at the mesh boundary. To demonstrate this new idea, we describe a 2D constrained Delaunay meshing algorithm that does not enforce strict ordering of vertex insertions near the mesh boundary. We prove that the sequential version of this algorithm generates a mesh in which the circumradius to shortest edge ratio of every triangle is √ 2 or greater, as long as every angle interior to the polygonal input domain is at least 90. We briefly touch upon the parallel version of this algorithm, but we relegate a more complete discussion (with extension to 3D) to a forthcoming paper.