Delaunay triangulation and the construction methods resulting in this triangulation have been extensive fields of research for a very long time. In particular, these topics are one of the major concerns in computational geometry (CG for short). It is therefore not really surprising to find a great deal of literature about Delaunay triangulation, starting with the pioneering paper by Delaunay himself, [Delaunay-1934]. Relevant references include [Shamos, Preparata-1985], [Joe-1991], [Fortune-1992], [Rajan-1994], [Boissonnat, Yvinec-1995] together with [Ruppert-1995] among various others. Delaunay triangulation problems are of interest for a number of reasons. Firstly, numerous theoretical issues can be investigated. Then, a wide range of applications in various disciplines exists including many engineering problems where theoretical results are used or revisited so as to obtain concrete algorithms.

Delaunay triangulation problems are of great interest as they can serve to support efficient and flexible mesh generation methods. In this respect, people concerned with engineering applications have investigated Delaunay-based mesh generation methods. The main references for this topic include [Lawson-1977], [Hermeline-1980], [Watson-1981], [Bowyer-1981] in the early 1980s and many others in the next decade such as [Weatherill-1985], [Mavriplis-1990], together with [George, Borouchaki-1997].

This chapter includes six parts. The first recalls some theoretical issues regarding Delaunay triangulation. The second discusses the notion of a constrained triangulation. We then show how to develop a Delaunay-type mesh generation method. The fourth part briefly introduces several variants. Finally, extensions are proposed. We explain how to complete a mesh conforming to a pre-specified size map and how to generate anisotropic meshes...