کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
514663 | 866789 | 2010 | 18 صفحه PDF | دانلود رایگان |

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 sequential point placement strategies for guaranteed quality mesh refinement: instead of a specific position for a new point, we derive two types of two-dimensional regions which we call selection disks. Both types of selection disks are inside the circumdisk of a poor quality triangle, with the Type I disk always inside the Type II disk. We prove that any point placement algorithm which inserts Steiner points inside selection disks of Type I terminates, and any algorithm which inserts Steiner points inside selection disks of Type II produces an asymptotically size-optimal mesh. In the area of parallel Delaunay mesh refinement, we develop a new theoretical framework for the construction of graded meshes on parallel architectures, i.e., for parallel mesh generation 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 parallel 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.
Journal: Finite Elements in Analysis and Design - Volume 46, Issues 1–2, January–February 2010, Pages 96–113