Editing Delaunay triangulation (section)

{{short description|Triangulation method}}{{broader|Triangulation (geometry)}}
[[File:Delaunay_circumcircles_vectorial.svg|right|thumb|280px|A Delaunay triangulation in the plane with circumcircles shown]] 

In [[computational geometry]], a '''Delaunay triangulation''' or '''Delone triangulation''' of a set of points in the plane subdivides their [[convex hull]]<ref>Loosely speaking, the region that a rubber band stretched around the points would enclose.</ref> into triangles whose [[Circumcircle#Triangles|circumcircle]]s do not contain any of the points; that is, each circumcircle has its generating points on its circumference, but all other points in the set are outside of it. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid [[sliver triangle]]s.

The triangulation is named after [[Boris Delaunay]] for his work on it from 1934.{{r|Delaunay1934}}

If the points all lie on a straight line, the notion of triangulation becomes [[Degeneracy (mathematics)|degenerate]] and there is no Delaunay triangulation. For four or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the [[Quadrilateral|quadrangle]] into two triangles satisfies the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors.

By considering circumscribed spheres, the notion of Delaunay triangulation extends to three and higher dimensions.  Generalizations are possible to [[metric (mathematics)|metrics]] other than [[Euclidean distance]]. However, in these cases a Delaunay triangulation is not guaranteed to exist or be unique.