Adaptive Dynamic Projection-Based Partitioning for Parallel Delaunay Mesh Generation Algorithms
Clemens Kadow · 2003
Meshes of high quality are an important ingredient for many applications in scientific computing. An accurate discretization of the problem geometry with elements of good aspect ratio is required by many numerical methods. In the finite element method, for example, interpolation error is related to the largest element angle in the mesh [1]. There is a critical need for algorithms that can generate meshes of provably high quality. For large-scale problems that require frequent remeshing (such as problems with evolving geometry), these algorithms must run in parallel on distributed memory machines. Whereas in recent years great strides have been made in parallel solvers, automatic parallel mesh generation for arbitrary domains remains an unsolved problem. Delaunay Refinement has proven useful for generating meshes of good aspect ratio. Provably good working algorithms that generate meshes for arbitrary domains exist in two dimensions. Efficient sequential implementations are available [2,3]. In three dimensions the problem is more challenging. Recent theoretical results [4] suggest algorithms to solve the general three dimensional meshing problem, but all sequential implementations available today can only cope with input that respects large angle bounds. Delaunay Refinement algorithms generate a Delaunay triangulation of the input vertices. New vertices are then