Delaunay triangulation

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)