View article

The study of algorithms for generating unstructured meshes of triangles and tetrahedra began with mechanical and aeronautical engineers who decompose physical domains into grids for the finite element and finite volume methods. Very soon, these engineers were joined by surveyors and specialists in geographical information systems, who use meshes called “triangulated irregular networks” to interpolate altitude fields on terrains, in the service of mapmaking, contouring, and visualization of topography. More recently, triangular meshes of surfaces have become prevalent as geometric models in computer graphics. These three groups of customers are the most numerous, but hardly the only ones; triangulations are found in most applications of multivariate interpolation. Unfortunately, it is fiendishly hard to implement a reliable mesh generator. The demands on a mesh are heavy: it must conform to the geometric …