Overview

Before going further, it seems important to clarify the terminology and to provide some basic definitions together with some notions of general interest. First, we define the covering-up of a bounded domain, then we present the notion of a triangulation before introducing a particular triangulation, namely the well-known Delaunay triangulation.

A domain covering-up simply corresponds to the naive meaning of this word and the term may be taken at face value. On the other hand, a triangulation is a specific covering-up that has certain specific properties. Triangulation problems concern the construction, of a covering-up of the convex hull of a given set of points. In general, a triangulation is a set of simplices, triangles in two dimensions, tetrahedra in three dimensions, with certain properties. If, in addition to a set of vertices, the boundary of a domain (more precisely a discretization of this boundary whose vertices are in the above set) is specified or, simply if any set of required edges (faces) is provided, we encounter a problem of constrained triangulation. In this case, the expected triangulation of the convex hull must contain these required items.

In contrast, the notion of a mesh may now be specified. Given a domain, namely defined by a discretization of its boundary, the problem comes down to constructing a "triangulation" that accurately matches this specific domain. In a way, we are dealing with a constrained triangulation but, now, we no longer face a convex hull problem and, moreover,...