A Delaunay triangulation in the plane with circumcircles shown

In mathematics, and computational geometry, a Delaunay triangulation or Delone triangularization 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 "sliver" triangles. The triangulation was invented by Boris Delaunay in 1934 ^[1]. Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... In computer science, computational geometry is the study of algorithms to solve problems stated in terms of geometry. ... In advanced geometry, in the most general meaning, triangulation is a subdivision of a geometric object into simplices. ... In geometry, a circumcircle of a given two-dimensional geometric shape is the smallest circle which contains the shape completely within it. ... For alternate meanings, such as the musical instrument, see triangle (disambiguation). ... Boris Nikolaevich Delaunay (March 15, 1890 in Petersburg – July 17, 1980 in Moscow) (or Delone; Russian language: Борис Николаевич Делоне), was a Soviet/Russian mathematician. ...

Based on Delaunay's definition^[1], the circumcircle of a triangle formed by three points from the original point set is empty if it does not contain vertices other than the three that define it (other points are permitted only on the very perimeter, not inside).

The Delaunay condition states that a triangle net is a Delaunay triangulation if all the circumcircles of all the triangles in the net are empty. This is the original definition for bidimensional spaces. It is possible to use it in tridimensional spaces by using a circumscribed sphere in place of the circumference.

For a set of points on the same line there is no Delaunay triangulation (in fact, the notion of triangulation is undefined for this case).

For 4 points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: clearly, the two possible triangulations that split the quadrangle into two triangles satisfy the Delaunay condition.

Generalizations are possible to metrics other than Euclidean. However in these cases a Delaunay triangulation is not guaranteed to exist or be unique.

Relationship with the Voronoi diagram

The Delaunay triangulation of a discrete point set P corresponds to the dual graph of the Voronoi tessellation for P. Triangulation can be used to find the distance from the shore to the ship. ... In topology and related fields of mathematics, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are isolated from each other in a certain sense. ... G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ... This is the Voronoi diagram of a random set of points in the plane (all points lie within the image). ...

The Delaunay triangulation with all the circumcircles and their centers (in red). Image File history File links No higher resolution available. ...

Connecting the centers of the circumcicles the Voronoi diagram is produced (in red). Image File history File links No higher resolution available. ...

n-dimensional Delaunay

For a set P of points in the (n-dimensional) Euclidean space, a Delaunay triangulation is a triangulation DT(P) such that no point in P is inside the circum-hypersphere of any simplex in DT(P). Around 300 BC, the Greek mathematician Euclid laid down the rules of what has now come to be called Euclidean geometry, which is the study of the relationships between angles and distances in space. ... Triangulation can be used to find the distance from the shore to the ship. ... In geometry, a circumcircle of a given two-dimensional geometric shape is the smallest circle which contains the shape completely within it. ... A 3-simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) or n-simplex is an n-dimensional analogue of a triangle. ...

It is known that there exists a unique Delaunay triangulation for P, if P is a set of points in general position; that is, no three points are on the same line and no four are on the same circle, for a two dimensional set of points, or no n + 1 points are on the same hyperplane and no n + 2 points are on the same hypersphere, for an n-dimensional set of points. An elegant proof of this fact is outlined below. It is worth mentioning, because it reveals connections between the two constructs fundamental for computational and combinatorial geometry. In geometry, general position for a set of points, or other configuration, means the general case situation, as opposed to some more special or coincidental cases that are possible. ... In computer science, computational geometry is the study of algorithms to solve problems stated in terms of geometry. ... Discrete geometry or combinatorial geometry may be loosely defined as study of geometrical objects and properties that are discrete or combinatorial, either by their nature or by their representation; the study that does not essentially rely on the notion of continuity. ...

The problem of finding the Delaunay triangulation of a set of points in n-dimensional Euclidean space can be converted to the problem of finding the convex hull of a set of points in (n + 1)-dimensional space, by giving each point p an extra coordinate equal to | p | ², taking the bottom side of the convex hull, and mapping back to n-dimensional space by deleting the last coordinate. As the convex hull is unique, so is the triangulation, assuming all facets of the convex hull are simplices. A facet not being a simplex implies that n + 2 of the original points lay on the same d-hypersphere, and the points were not in general position. Convex hull: elastic band analogy In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X. // For planar objects, i. ... A 3-simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) or n-simplex is an n-dimensional analogue of a triangle. ... 2-sphere wireframe as an orthogonal projection Just as a stereographic projection can project a spheres surface to a plane, it can also project a 3-spheres surface into 3-space. ...

Properties

Let n be the number of points and d the number of dimensions.

• The union of all simplices in the triangulation is the convex hull of the points.
• The Delaunay triangulation contains at most simplices.
• In the plane (d = 2), if there are b vertices on the convex hull, then any triangulation of the points has at most 2n − 2 − b triangles, plus one exterior face (see Euler characteristic).
• The Delaunay triangulation maximizes the minimum angle. Compared to any other triangulation of the points, the smallest angle in the Delaunay triangulation is at least as large as the smallest angle in any other. However, the Delaunay triangulation does not necessarily minimize the maximum angle.
• A circle circumscribing any Delaunay triangle does not contain any other input points in its interior.
• If a circle passing through two of the input points doesn't contain any other of them in its interior, then the segment connecting the two points is an edge of a Delaunay triangulation of the given points.
• The Delaunay triangulation of a set of points in d-dimensional spaces is the projection of the convex hull of the projections of the points onto a (d+1)-dimensional paraboloid.

In algebraic topology, the Euler characteristic is a topological invariant, a number that describes one aspect of a topological spaces shape or structure. ... Convex hull: elastic band analogy In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X. // For planar objects, i. ... Paraboloid of revolution Hyperbolic paraboloid In mathematics, a paraboloid is a quadric, a type of surface in three dimensions, described by the equation: (elliptic paraboloid), or (hyperbolic paraboloid). ...

Visual Delaunay definition: Flipping

From the above properties an important feature arises: Looking at two triangles ABD and BCD with the common edge BD (see figures), if the sum of the angles α and γ is less or equal than 180°, the triangles meet the Delaunay condition.

This is an important property because it allows the use of a flipping technique. If two triangles do not meet the Delaunay condition, switching the common edge BD for the common edge AC produces two triangles that do meet the Delaunay condition :

This triangulation does not meet the Delaunay condition (the sum of α and γ is bigger than 180°). Image File history File links No higher resolution available. ...

This triangulation does not meet the Delaunay condition (the circumferences contain more than 3 points). Image File history File links No higher resolution available. ...

Flipping the common edge produces a Delaunay triangulation for the four points. Image File history File links No higher resolution available. ...

Algorithms

All algorithms for computing Delaunay triangulations rely on fast operations for detecting when a point is within a triangle's circumcircle and an efficient data structure for storing triangles and edges. In two dimensions, one way to detect if point D lies in the circumcircle of A, B, C is to evaluate the determinant: In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...

Assuming A, B and C to lie counter-clockwise, this is positive if and only if D lies in the circumcircle. A clockwise motion is one that proceeds like the clocks hands: from the top to the right, then down and then to the left, and back to the top. ...

Incremental

The most straightforward way of computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph. When a vertex is added, a search is done for all triangles' circumcircles containing the vertex. Then, those triangles are removed and that part of the graph retriangulated. Done naively, this results in a running time of O(n²).

A common way to speed up this method is sweepline, which involves sorting the vertices by one coordinate and adding them in that order. Then, one only needs to keep track of circumcircles containing points of large enough first coordinate. The expected running time in two dimensions in this case is O(n^3/2) although the worst case continues to be O(n²). Its performance at low numbers of points is competitive with divide and conquer (below) but does not scale as nicely above the tens of thousands of points. ^[2] In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. ...

If one inserts the vertices in a random order, the expected running time is O(n log n).

Another efficient O(n log n) incremental algorithm keeps the whole history of the triangulation in the form of a tree. The elements replacing a conflicting element in an insertion are called its children. When a parent is in conflict with a point to be inserted, so are its children. This provides a fast way of getting the list of triangles to remove (which is the slowest part of any incremental insertion algorithm).

Divide and conquer

A divide and conquer algorithm for triangulations in two dimensions is due to Lee and Schachter which was improved by Guibas and Stolfi^[3] and later by Dwyer. In this algorithm, one recursively draws a line to split the vertices into two sets. The Delaunay triangulation is computed for each set, and then the two sets are merged along the splitting line. Using some clever tricks, the merge operation can be done in time O(n), so the total running time is O(n log n).^[4] In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ...

For certain types of point sets, such as a uniform random distribution, by intelligently picking the splitting lines the expected time can be reduced to O(n log log n) while still maintaining worst-case performance.

A divide and conquer paradigm to performing a triangulation in d-dimensions is presented in "DeWall: A Fast Divide & Conquer Delaunay Triangulation Algorithm in E^d" by P. Cignoni, C. Montani, R. Scopigno.

Applications

The Euclidean minimum spanning tree of a set of points is a subset of the Delaunay triangulation of the same points, and this can be exploited to compute it efficiently. An EMST computed and drawn by Leda, a C++ commercial algorithm library; see the External Links section The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane, where the weight of the edge between each pair of points is the...

For modeling terrain or other objects given a set of sample points, the Delaunay triangulation gives a nice set of triangles to use as polygons in the model. In particular, the Delaunay triangulation avoids narrow triangles (as they have large circumcircles compared to their area).

The Delaunay triangulation of a random set of 100 points in a plane.

Delaunay triangulations are often used to build meshes for the finite element method, because of the angle guarantee and the fact that we know fast triangulation algorithms. Typically, the domain to be meshed is specified as a coarse simplicial complex; for the mesh to be numerically stable, it must be refined, for instance by using Ruppert's algorithm. This has been implemented by Jonathan Shewchuk in the freely available (yet non-free) Triangle package. Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Mathematically, the finite element method (FEM) is used for finding approximate solution of partial differential equations (PDE) as well as of integral equations such as the heat transport equation. ... In mathematics, a simplicial complex is a topological space of a particular kind, built up of points, line segments, triangles, and their n-dimensional counterparts. ... Rupperts algorithm (also known as Delaunay Refinement) is an algorithm for creating quality Delaunay triangulations. ... Jonathan Richard Shewchuk is an Associate Professor in Computer Science at the University of California, Berkeley. ... Free software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions only to ensure that further recipients can also do these things. ...

See also

• Voronoi diagram
• Gabriel graph
• Pitteway triangulation

This is the Voronoi diagram of a random set of points in the plane (all points lie within the image). ... Points a and b are Gabriel neighbours, as c is outside their diameter circle. ... Left: A Pitteway triangulation. ...

References

1. ^ ^{a b} B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793-800, 1934
2. ^ http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
3. ^ Computing Constrained Delaunay Triangulations
4. ^ G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. June 1992

External links

• Real time interactive Voronoi and Delaunay diagrams with source code
• 2D, 3D, and higher dimensional Delaunay triangulation in CGAL, the Computational Geometry Algorithms Library
• Applet for calculation and visualization of convex hull, Delaunay triangulations and Voronoi diagrams in space
• 2D C Delaunay code and Java applet
• C++ 2D Delaunay code
• Mathworld on Delaunay triangulation
• Qhull for computing Delaunay triangulations in 2-d, 3-d, etc.
• Triangle, a 2D Quality Mesh Generator and Delaunay Triangulator
• Triangulate, an efficient algorithm for Terrain Modelling
• G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. (June 1992)