Namespaces
Variants
Actions

Difference between revisions of "Delaunay triangulation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
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''
 
''Delone triangulation''
  
 
A very important geometric structure in [[Computational geometry|computational geometry]], named after B.N. Delaunay.
 
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" />.
+
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 <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.
+
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====
 
====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>
 
<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>

Latest revision as of 17:32, 5 June 2020


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 $ { \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

[a1] F.P. Preparata, M.I. Shamos, "Computational geometry: an introduction" , Springer (1985)
[a2] H. Edelsbrunner, "Algorithms in combinatorial geometry" , Springer (1987)
[a3] A. Okabe, B. Boots, K. Sugihara, "Spatial tessellations: concepts and applications of Voronoi diagrams" , Wiley (1992)
How to Cite This Entry:
Delaunay triangulation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Delaunay_triangulation&oldid=46621
This article was adapted from an original article by O.R. Musin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article