In the previous chapter, a very useful and practical topic was covered—namely, the decomposition of a simple polygon into triangles. In this chapter, we consider the triangulation of a set of points in the plane, which is used to solve a significant number of problems in science and engineering [39, 54]. Delaunay triangulation is named after the Russian mathematician Boris Nikolaevich Delaunay (1890–1980), who studied optimal methods for dividing space into simple geometric structures. This triangulation plays a key role in computational geometry, computer graphics, geographic information systems, and numerical simulations. Its most important feature is that it maximizes the minimum interior angle among all possible triangulations of a given set of points, thereby avoiding the formation of extremely elongated triangles and achieving better regularity. Such triangulations can also be used to create models of a region on Earth. The generated model should be able to respond or estimate, at any point within a given region, the elevation, temperature, or air pressure. If the terrain is described by some function \(f:A \subset {\mathbb{R}}^{3} \to {\mathbb{R}}\) , which assigns to each element a from the domain \({\text{A}}\) a height value \(f(a) \in {\mathbb{R}}\) , then due to the uncountability and infiniteness of the set A, it is not possible to measure the height f(a) for every \(a \in A\) —they can only be estimated (see Fig. 6.1a).