Mesh Generation and Optimal Triangulation

Computing in Euclidean Geometry Eds. D.Z. Du and F.K. Hwang, World Scientific Publishing Co., pp.23-90

MESHING
RESEARCH
CORNER

Dept. of Information and Computer Science, University of California Irvine, California 92717-3425, U.S.A.

Abstract
We survey the computational geometry relevant to finite-element mesh generation. We especially focus on optimal triangulations of geometric domains in two- and three-dimensions. An optimal triangulation is a partition of the domain into triangles or tetrahedra, that is best according to some criterion that measures the size, shape, or number of triangles. We discuss algorithms both for the optimization of triangulations on a fixed set of vertices and for the placement of new vertices (Steiner points). We briefly survey the heuristic algorithms used in some practical mesh generators.