View source for Delaunay triangulation

''Delone triangulation''

A very important geometric structure in [[Computational geometry|computational geometry]], named after B.N. Delaunay.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101301.png" /> be a generic set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101302.png" /> points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101303.png" />. The straight-line dual of the [[Voronoi diagram|Voronoi diagram]] generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101304.png" /> is a [[Triangulation|triangulation]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101305.png" />, called the Delaunay triangulation and usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101306.png" />. The Delaunay triangulation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101307.png" /> is triangulation of the convex hull of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101308.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d1101309.png" /> and the set of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013010.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013011.png" />.

One of the equivalent definitions for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013012.png" /> is as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013013.png" /> is a triangulation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013014.png" /> satisfying the  "empty sphere propertyempty sphere property" , i.e. no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013015.png" />-simplex of the triangulation of its circumsphere has a point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110130/d11013016.png" /> in its interior.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.P. Preparata,   M.I. Shamos,   "Computational geometry: an introduction" , Springer  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Edelsbrunner,   "Algorithms in combinatorial geometry" , Springer  (1987)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Okabe,   B. Boots,   K. Sugihara,   "Spatial tessellations: concepts and applications of Voronoi diagrams" , Wiley  (1992)</TD></TR></table>