ABSTRACT
The Delaunay triangulation is a geometric structure that engineers have used for meshes since mesh generation was in its infancy. In two dimensions, it has a striking advantage: among all possible triangulations of a fixed set of points, the Delaunay triangulation maximizes the minimum angle. It also optimizes several other geometric criteria related to interpolation accuracy. If it is our goal to create a triangulation without small angles, it seems almost silly to consider a triangulation that is not Delaunay. Delaunay triangulations have been studied thoroughly, and excellent algorithms are available for constructing and updating them.
