Delaunay triangulation

related topics
{math, number, function}
{math, energy, light}
{line, north, south}
{@card@, make, design}
{rate, high, increase}

In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles. The triangulation was invented by Boris Delaunay in 1934[1].

For a set of points on the same line there is no Delaunay triangulation. (The notion of triangulation is degenerate for this case.) For four points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: the two possible triangulations that split the quadrangle into two triangles satisfy the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors.

By considering circumscribed spheres, the notion of Delaunay triangulation extends to three and higher dimensions. Generalizations are possible to metrics other than Euclidean. However in these cases a Delaunay triangulation is not guaranteed to exist or be unique.

Contents

Relationship with the Voronoi diagram

The Delaunay triangulation of a discrete point set P in general position corresponds to the dual graph of the Voronoi tessellation for P. Special cases include the existence of three points on a line and four points on circle.

The Delaunay triangulation with all the circumcircles and their centers (in red).

Connecting the centers of the circumcircles produces the Voronoi diagram (in red).

n-dimensional Delaunay

Full article ▸

related documents
Pell's equation
Fundamental theorem of arithmetic
Scientific notation
Curve
Brouwer fixed point theorem
Selection sort
Naive Bayes classifier
Tensor
Affine transformation
Binomial theorem
Grover's algorithm
Shell sort
Greatest common divisor
Polish notation
Befunge
Knapsack problem
Tree automaton
Empty set
NP (complexity)
Net (mathematics)
Direct product
Root-finding algorithm
Brute force attack
Finite state machine
Symmetric matrix
Analytic function
Cyclic group
Graph theory
Ordered pair
Tangent space