View source for Delaunay triangulation

<!--
d1101301.png
$#A+1 = 16 n = 0
$#C+1 = 16 : ~/encyclopedia/old_files/data/D110/D.1100130 Delaunay triangulation,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''Delone triangulation''

A very important geometric structure in [[Computational geometry|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|Voronoi diagram]] generated by  $  S $
is a [[Triangulation|triangulation]] of  $  S $, 
called the Delaunay triangulation and usually denoted by  $  { \mathop{\rm 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====
<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>