Jim Ruppert

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-694
June 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-694.pdf

We present a simple new algorithm for triangulating polygons and planar straightline graphs. It provides "shape" and "size" guarantees:
* All triangles have a bounded aspect ratio.
* The number of "Steiner points" added is within a constant factor of optimal.

Such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. The technique we use -- successive refinement of the Delaunay triangulation -- extends a mesh generation technique of Chew by allowing triangles that vary in size. Previous algorithms with shape and size bounds have all been based on quadtrees. The Delaunay refinement algorithm matches their bounds, but uses a fundamentally different approach. It is much simpler, and hence easier to implement, and it generally produces smaller meshes in practice.

BibTeX citation:

@techreport{Ruppert:CSD-92-694,
    Author = {Ruppert, Jim},
    Title = {A New and Simple Algorithm for Quality 2-Dimensional Mesh Generation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6268.html},
    Number = {UCB/CSD-92-694},
    Abstract = {We present a simple new algorithm for triangulating polygons and planar straightline graphs. It provides "shape" and "size" guarantees:   <br />* All triangles have a bounded aspect ratio.  <br />* The number of "Steiner points" added is within a constant factor of optimal.   <p>Such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. The technique we use -- successive refinement of the Delaunay triangulation -- extends a mesh generation technique of Chew by allowing triangles that vary in size. Previous algorithms with shape and size bounds have all been based on quadtrees. The Delaunay refinement algorithm matches their bounds, but uses a fundamentally different approach. It is much simpler, and hence easier to implement, and it generally produces smaller meshes in practice.}
}

EndNote citation:

%0 Report
%A Ruppert, Jim
%T A New and Simple Algorithm for Quality 2-Dimensional Mesh Generation
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-694
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6268.html
%F Ruppert:CSD-92-694