Delaunay triangulation

Delone triangulation

A very important geometric structure in computational geometry, named after B.N. Delaunay.

Let $S=\{p_1\dots p_n\}$ be a generic set of $n$ points in ${\mathbf{R}}^d$. The straight-line dual of the Voronoi diagram generated by $S$ is a triangulation of $S$, called the Delaunay triangulation and usually denoted by $\mathrm{DT}(S)$. The Delaunay triangulation of $S$ is triangulation of the convex hull of $S$ in ${\mathbf{R}}^d$ and the set of vertices of $DT(S)$ is $S$.

One of the equivalent definitions for $DT(S)$ is as follows: $DT(S)$ is a triangulation of $S$ satisfying the "empty sphere propertyempty sphere property" , i.e. no $d$- simplex of the triangulation of its circumsphere has a point of $S$ in its interior.

References[edit]