Delaunay Triangulation

A Delaunay triangulation divides the convex hull of a set of points into triangles so that no point in the set lies inside the circumcircle of any triangle, a property called the empty circumcircle property. This same requirement maximizes the size of the smallest angle among all the triangles in the triangulation, which tends to avoid long, thin sliver triangles. The construction is named after the mathematician Boris Delaunay, who introduced it in 1934, and it is a foundational tool in computational geometry, used for tasks such as mesh generation and terrain modeling because of its well shaped, angle maximizing triangles.