Delaunay Triangulation

From GM-RKB
(Redirected from Delaunay triangulation)
Jump to navigation Jump to search

A Delaunay Triangulation is a triangulation of a collection of graph edges that satisfies the empty circle property



References

2017a

  • (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Delaunay_triangulation Retrieved:2017-6-18.
    • In mathematics and computational geometry, 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 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 is named after Boris Delaunay for his work on this topic from 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 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 distance. However, in these cases a Delaunay triangulation is not guaranteed to exist or be unique.

  1. Delaunay, Boris (1934). "Sur la sphère vide". Bulletin de l'Académie des Sciences de l'URSS, Classe des sciences mathématiques et naturelles. 6: 793–800.

2017b

2017c

  • (Eppstein, 2017) ⇒ David Eppstein, Theory Group, ICS, UC Irvine. Geometry in Action: Delaunay Triangulation https://www.ics.uci.edu/~eppstein/gina/delaunay.html Retrieved:2017-6-18.
    • The Delaunay triangulation of a point set is a collection of edges satisfying an "empty circle" property: for each edge we can find a circle containing the edge's endpoints but not containing any other points. These diagrams their and their duals (Voronoi diagrams and medial axes)) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. The Delaunay triangulation is also closely related by the so-called "lifting transformation" to convex hulls in one higher dimension. Many common methods for function interpolation and mesh generation are based in some way on Delaunay triangulations, but there are also many other ways in which this structure has been applied.

2017D

  • (Pless, 2017) ⇒ Robert Pless - Lecture 17: Voronoi Diagrams and Delauney Triangulations. https://research.engineering.wustl.edu/~pless/506/l17.html Retrieved:2017-6-18.
    • Delaunay Triangulations: Last time we gave an algorithm for computing Voronoi diagrams. Today we consider the related structure, called a Delaunay triangulation (DT). Since the Voronoi diagram is a planar graph, we may naturally ask what is the corresponding dual graph. The vertices for this dual graph can be taken to be the sites themselves. Since (assuming general position) the vertices of the Voronoi diagram are of degree three, it follows that the faces of the dual graph (excluding the exterior face) will be triangles. The resulting dual graph is a triangulation of the sites, the Delaunay triangulation.

      Delaunay triangulations have a number of interesting properties, that are consequences of the structure of the Voronoi diagram.

2012

2001

1980

1934

  • (Delaunay, 1934) ⇒ B. Delaunay, (1934). "Sur la sphere vide". A la memoire de Georges Voronoi, Bulletin de l’Academie des Sciences de l’URSS. Classe des sciences mathematiques et na, Issue 6, 793–800