Guaranteed-Quality Triangular Meshes
Chew, Paul L.
Department of Computer Science Tech Report 89-983, Cornell University, 1989
There are a number of applications for which it is desirable to divide a given region in a 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 bound are best if all triangles are as close as possible to equilateral triangles. Presently, either these triangulations are produced by hand or they are produced automatically using any one of a number of hueristic techniques. For these hueristic techniques, certain cases can require human intervantion to illiminate 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 resulting triangles are all between 30 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 the final number of triangles, and (2) the user can control the element density, producing smaller triangles in areas where more accuracy is desired.
Contact author(s) or publisher for availability and copyright information on above referenced article