Guaranteed-Quality Triangular Meshes

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 and 120 degs 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.

This publication has 0 references indexed in Scilit: