Delaunay triangulation - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

and computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, a Delaunay triangulation for a set P of points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle

Triangle

A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....

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

Boris Delaunay

Boris Nikolaevich Delaunay or Delone was one of the first Russian mountain climbers and a Soviet/Russian mathematician, and the father of physicist Nikolai Borisovich Delone....

in 1934.

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 or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies 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.

Relationship with the Voronoi diagram

The Delaunay triangulation of a discrete

Discrete space

In topology, 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.- Definitions :Given a set X:...

point set P in general position

General position

In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...

corresponds to the dual graph

Dual graph

In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...

of the Voronoi tessellation for P. Special cases include the existence of three points on a line and four points on circle.

d-dimensional Delaunay

For a set P of points in the (d-dimensional) Euclidean space

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

, a Delaunay triangulation is a triangulation DT(P) such that no point in P is inside the circum-hypersphere of any simplex

Simplex

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...

in DT(P). It is known that there exists a unique Delaunay triangulation for P, if P is a set of points in general position
General position
In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...

; that is, there exists no k-flat

Flat (geometry)

In geometry, a flat is a subset of n-dimensional space that is congruent to a Euclidean space of lower dimension. The flats in two-dimensional space are points and lines, and the flats in three-dimensional space are points, lines, and planes....

containing k + 2 points nor a k-sphere containing k + 3 points, for 1 ≤ k ≤ d − 1 (e.g., for a set of points in ℝ³; no three points are on a line, no four on a plane, no four are on a circle, and no five on a sphere).

The problem of finding the Delaunay triangulation of a set of points in d-dimensional Euclidean space can be converted to the problem of finding the convex hull

Convex hull

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....

of a set of points in (d + 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 d-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

Simplex

. Nonsimplicial facets only occur when d + 2 of the original points lie on the same d-hypersphere

Hypersphere

In mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...

, i.e., the points are not in general position.

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 O(n^{⌈d / 2⌉}) 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
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...

).
In the plane, each vertex has on average six surrounding triangles.
In the plane, 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 points of convex hull
Convex hull
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....

onto a (d + 1)-dimensional paraboloid
Paraboloid
In mathematics, a paraboloid is a quadric surface of special kind. There are two kinds of paraboloids: elliptic and hyperbolic. The elliptic paraboloid is shaped like an oval cup and can have a maximum or minimum point....

.
The closest neighbor b to any point p is on an edge bp in the Delaunay triangulation since the nearest neighbor graph
Nearest neighbor graph
The nearest neighbor graph for a set of n objects P in a metric space is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points...

is a subgraph of the Delaunay triangulation.

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 than or equal to 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:

Algorithms

Many 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

Determinant

In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

When A, B and C are sorted in a counterclockwise order, this determinant is positive if and only if D lies inside the circumcircle.

Flip algorithms

As mentioned above, if a triangle is non-Delaunay, we can flip one of its edges. This leads to a straightforward algorithm: construct any triangulation of the points, and then flip edges until no triangle is non-Delaunay. Unfortunately, this can take O(n²) edge flips, and does not extend to three dimensions or higher.

Incremental

The most straightforward way of efficiently computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph. When a vertex v is added, we split in three the triangle that contains v, then we apply the flip algorithm. Done naively, this will take O(n) time: we search through all the triangles to find the one that contains v, then we potentially flip away every triangle. Then the overall runtime is O(n²).

If we insert vertices in random order, it turns out (by a somewhat intricate proof) that each insertion will flip, on average, only O(1) triangles – although sometimes it will flip many more.
This still leaves the point location time to improve. We can store the history of the splits and flips performed: each triangle stores a pointer to the two or three triangles that replaced it. To find the triangle that contains v, we start at a root triangle, and follow the pointer that points to a triangle that contains v, until we find a triangle that has not yet been replaced. On average, this will also take O(log n) time. Over all vertices, then, this takes O(n log n) time. While the technique extends to higher dimension (as proved by Edelsbrunner and Shah), the runtime can be exponential in the dimension even if the final Delaunay triangulation is small.

The Bowyer–Watson algorithm provides another approach for incremental construction. It gives an alternative to edge flipping for computing the Delaunay triangles containing a newly inserted vertex.

Divide and conquer

A divide and conquer algorithm

Divide and conquer algorithm

In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...

for triangulations in two dimensions is due to Lee and Schachter which was improved by Guibas

Leonidas J. Guibas

Leonidas John Guibas is a professor of computer science at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth at Stanford, where he received his Ph.D. in 1976...

and Stolfi

Jorge Stolfi

Jorge Stolfi is a full professor of computer science at the State University of Campinas, working in computer vision, image processing, splines and other function approximation methods, graph theory, computational geometry, and several other fields...

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).

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 and conquer Delaunay triangulation algorithm in E^d" by P. Cignoni, C. Montani, R. Scopigno.

Divide and conquer has been shown to be the fastest DT generation technique.

Sweepline

Fortune's Algorithm

Fortune's algorithm

Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O time and O space...

uses a sweepline technique to achieve O(n log n) runtime in the planar case.

Sweephull

Sweephull is a fast hybrid technique for 2D Delaunay triangulation that uses a radially propagating sweep-hull (sequentially created from
the radially sorted set of 2D points, giving a non-overlapping triangulation), paired with a ﬁnal iterative triangle ﬂipping step.
Empirical results indicate the algorithm runs in approximately half the time of Qhull, and free implementations in C++ and C# are available.

Applications

The Euclidean minimum spanning tree

Euclidean minimum spanning tree

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...

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.

For modelling 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). See triangulated irregular network

Triangulated irregular network

A triangulated irregular network is a digital data structure used in a geographic information system for the representation of a surface...

.

Delaunay triangulations can be used to determine the density or intensity of points samplings by means of the DTFE

Delaunay tessellation field estimator

The Delaunay tessellation field estimator is a mathematical tool for reconstructing a volume-covering and continuous density or intensity field from a discrete point set...

Delaunay triangulations are often used to build meshes for space-discretised solvers such as the finite element method

Finite element method

The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...

and the finite volume method

Finite volume method

The finite volume method is a method for representing and evaluating partial differential equations in the form of algebraic equations [LeVeque, 2002; Toro, 1999]....

of physics simulation, because of the angle guarantee and because fast triangulation algorithms have been developed. Typically, the domain to be meshed is specified as a coarse simplicial complex

Simplicial complex

In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...

; for the mesh to be numerically stable, it must be refined, for instance by using Ruppert's algorithm

Ruppert's algorithm

In mesh generation, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm for creating quality Delaunay triangulations. The algorithm takes a planar straight-line graph and returns a conforming Delaunay triangulation of only quality triangles...

External links

Delaunay triangulation in CGAL
CGAL
The Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....

, the Computational Geometry Algorithms Library:
- - - - — Code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection – A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator – A C++ wrapper on Triangle – A sweepline Constrained Delaunay Triangulation (CDT) library, available in ActionScript 3, C, C++, C#, Go, Java, Javascript, Python and Ruby
        The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.