Andrey Chernikov and Nikos Chrisochoides.

16^th Annual Fall Workshop on Computational Geometry, Northampton, MA, November, 2006

We describe a complete solution for both sequential and parallel construction of guaranteed quality Delaunay meshes for general two-dimensional geometries. We generalize the existing single-core point placement strategies for guaranteed quality mesh re¯nement: instead of a specific position for a new point, we derive a selection disk inside the circumdisk of a poor quality triangle. We prove that any point placement algorithm which inserts a point inside the selection disk of a poor quality triangle will terminate and produce a guaranteed quality size-optimal mesh. In the area of parallel Delaunay mesh refinement, we develop a new theoretical framework for the construction of graded meshes on multi-core architectures, i.e., meshes with element size controlled by a user-defined criterion. Our sufficient conditions of point Delaunay-independence allow to select points for concurrent insertion in such a way that the standard sequential guaranteed quality Delaunay refinement procedures can be applied in parallel to attain the required element quality constraints. Finally, we present a novel multi-core algorithm which can be used in conjunction with any sequential point placement strategy that chooses points within the selection disks. We implemented our algorithm for shared memory multi-core architectures and present the experimental results. Our data show that even on workstations with a few cores, which are now in common use, our implementation is significantly faster than the best sequential counterpart.