Publication Details

 

 


 

Parallel Graded Generalized Delaunay Mesh Refinement

 

Andrey Chernikov and Nikos Chrisochoides.

 

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

 

Abstract

 

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 renement: 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.

 

 


 

  [PDF]          [BibTex] 

 

 

[Return to Publication List]