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[edit]