Namespaces
Variants
Actions

Delaunay triangulation

From Encyclopedia of Mathematics
Revision as of 17:00, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Delone triangulation

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

Let be a generic set of points in . The straight-line dual of the Voronoi diagram generated by is a triangulation of , called the Delaunay triangulation and usually denoted by . The Delaunay triangulation of is triangulation of the convex hull of in and the set of vertices of is .

One of the equivalent definitions for is as follows: is a triangulation of satisfying the "empty sphere propertyempty sphere property" , i.e. no -simplex of the triangulation of its circumsphere has a point of 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