Delaunay Triangulation - Applications

Applications

The Euclidean minimum spanning tree of a set of points is a subset of the Delaunay triangulation of the same points, and this can be exploited to compute it efficiently.

For modelling terrain or other objects given a set of sample points, the Delaunay triangulation gives a nice set of triangles to use as polygons in the model. In particular, the Delaunay triangulation avoids narrow triangles (as they have large circumcircles compared to their area). See triangulated irregular network.

Delaunay triangulations can be used to determine the density or intensity of points samplings by means of the DTFE.

Delaunay triangulations are often used to build meshes for space-discretised solvers such as the finite element method and the finite volume method of physics simulation, because of the angle guarantee and because fast triangulation algorithms have been developed. Typically, the domain to be meshed is specified as a coarse simplicial complex; for the mesh to be numerically stable, it must be refined, for instance by using Ruppert's algorithm.

With FEM/BEM increasing popularity comes the incentive to improve automatic meshing algorithms. However, all of these algorithms can create distorted and even unusable grid elements. Fortunately, several techniques exist which can take an existing mesh and improve its quality. For instance smoothing (also referred to as mesh refinement) is one of such methods, which repositions nodal locations, so as to minimize element distortion. The stretched grid method allows the obtaining of pseudo-regular meshes that meet the Delaunay criteria very easily and quickly in a one-step solution.