Delaunay triangulation

Remarks

Example: let $P = \set{(0,0), (2,0), (1,2)}$, a single triangle. Its only triangulation is the triangle itself, and the open circumdisk contains no point of $P$, since the three points lie on the circle.

Non-example: let $P = \set{(-2, 0), (2, 0), (0, 1), (0, -1)}$ and take the triangulation by the diagonal from $(-2, 0)$ to $(2, 0)$. The circumcircle of $(-2, 0), (2, 0), (0, 1)$ has centre $(0, -3/2)$ and radius $5/2$, and $(0, -1)$ is at distance $1/2$ from the centre, so it lies inside. The other diagonal, from $(0, 1)$ to $(0, -1)$, gives the Delaunay triangulation.

A Delaunay triangulation of $P$ always exists, and it is unique when no four points of $P$ lie on a common circle. Among all triangulations of $P$, a Delaunay triangulation maximizes the smallest angle of its triangles. When no four points are concyclic, two points of $P$ are joined by an edge exactly when their cells in the Voronoi diagram share an edge.