Delaunay triangulation

A Delaunay triangulation, also called a Delone triangulation, subdivides the convex hull of a set of points in the plane into triangles so that the circumcircle of every triangle contains none of the other points. This maximizes the smallest angle of any triangle and tends to avoid sliver triangles. It is named after Boris Delaunay for his work on it from 1934. If all points lie on a straight line the triangulation is degenerate, and when four or more points lie on one circle, such as the corners of a rectangle, the triangulation is not unique. The notion extends to spheres in three and higher dimensions. The Delaunay triangulation of points in general position is the dual graph of the Voronoi diagram of the same points, with the triangle circumcenters as the Voronoi vertices. A naive incremental construction takes quadratic time, while inserting vertices in random order and storing the history gives O(n log n) time overall.