A DELAUNAY REFINEMENT ALGORITHM FOR QUALITY 2-DIMENSIONAL MESH GENERATION

We present a simple new algorithm for triangulating polygons and plana r straightline graphs, It provides ''shape'' and ''size'' guarantees: All triangles have a bounded aspect ratio. The number of triangles is within a constant factor of optimal. Such ''quality'' triangulations a re desirable as meshes for the finite element method, in which the run ning time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. Th e technique we use-successive refinement of a Delaunay triangulation-e xtends a mesh generation technique of Chew by allowing triangles of va rying sizes. Compared with previous quadtree-based algorithms for qual ity mesh generation, the Delaunay refinement approach is much simpler and generally produces meshes with fewer triangles. We also discuss an implementation of the algorithm and evaluate its performance on a var iety of inputs. (C) 1995 Academic Press, Inc.