Guaranteed-Quality Triangular Meshes

TR 89-983, Department of Computer Science, Cornell University, Ithaca, NY, April 1989

MESHING
RESEARCH
CORNER

Pratt & Whitney East Hartford, CT 06108

Abstract
There are a number of applications for which it is desirable to divide a given region in the plane into nicely shaped triangles. One important such application is the finite element method, a method widely used to obtain approximate solutions to a wide variety of engineering problems. For this kind of application, not just any triangulation will do; error bounds are best if all the triangles are as close as possible to equilateral triangles. Presently, either these triangulations are produced by hand or they are produced automatically using one of a number of heuristic techniques. For these heuristic techniques, certain cases can require human intervention to eliminate flat triangles. In this paper, we present an efficient new technique (based on Delaunay triangulations) for automatically producing desirable triangulations. Unlike most previous techniques, this one comes with a guarantee: the angles in the resulting triangles are all between 30 degrees and 120 degrees, and the edge lengths are all between h and 2h where h is a parameter chosen by the user. Additional useful properties include (1) the worst-case time to produce a triangulation is linear in the final number of triangles, and (2) the user can control the element density, producing smaller triangles in areas where more accuracy is desired.

Work on this paper has been supported by NSF grant DMC-86-17355, ONR grant N001486-K-0281, and DARPA under ONR contract N0014-88-K-0591.