Namespaces
Variants
Actions

Delaunay triangulation

From Encyclopedia of Mathematics
Jump to: navigation, search


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