A mesh is an approximation of a domain into simple elements called simplexes ': triangles in the plane, tetrahedrons in dimension 3 and their analogues in higher dimensions. The quality of the approximation depends on the shape of the simplexes used. An important issue is the construction of "good" triangulations, i.e. triangulations whose elements are not too flattened and have sufficiently large dihedral angles. This issue is central to the production of realistic computer graphics and the simulation of complex physical phenomena.
This lecture first shows that, for a given set of points, Delaunay triangulation is optimal from several points of view. The quality of a mesh can be improved by choosing the position of its vertices. We introduce the notion of ε-net, which characterizes the quality of a finite set of points sampling a domain. We show that such samples can be constructed efficiently in all dimensions. This result is sufficient in dimension 2 to ensure that the Delaunay triangulation of such samples is good, making it very useful in practice. Unfortunately, this property is not true in dimension 3 and beyond: three-dimensional triangulations can contain very flattened simplexes, regardless of mesh refinement. While the problem is well known, both to mathematicians seeking to establish guarantees and to engineers using these meshes for calculations, it is very difficult to solve. This lecture presents some of the theoretical advances achieved over the last ten years, as well as some effective heuristic solutions. In particular, it presents a randomized algorithm for constructing good Delaunay triangulations in all dimensions. The algorithm is based on an algorithmic version of the local Lovász lemma, a major algorithmic result by Moser and Tardos.
