Delaunay Triangulation
A Delaunay Triangulation is a triangulation of a collection of graph edges that satisfies the empty circle property
- See: Voronoi Diagram, Euclidean Distance, Mathematics, Computational Geometry, Triangulation (Geometry), Circumcircle#Triangles, Triangle, Sliver Triangle, Boris Delaunay, Quadrilateral, Metric (Mathematics).
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.
- 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]
- ↑ 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
- (Wikibooks, 2017) ⇒ https://en.wikibooks.org/wiki/Trigonometry/For_Enthusiasts/Delaunay_triangulation Retrieved:2017-6-18.
- A Delaunay triangulation is a particular way of joining a set of points to make a triangular mesh. Delaunay triangulations tend to avoid skinny triangles. The triangulation was invented by Boris Delaunay in 1934.
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.
- 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.
2012
- (Liebling & Pournin, 2012) ⇒ Liebling, T. M., & Pournin, L. (2012). Voronoi diagrams and Delaunay triangulations: Ubiquitous siamese twins. Documenta Mathematics, ISMP, 419-431.
- QUOTE: A Voronoi diagram induced by a finite set A of sites is a decomposition of the plane into possibly unbounded (convex) polygons called Voronoi regions, each consisting of those points at least as close to some particular site as to the others.
The dual Delaunay triangulation associated to the same set A of sites is obtained by drawing a triangle edge between every pair of sites whose corresponding Voronoi regions are themselves adjacent along an edge. Boris Delaunay has equivalently characterized these triangulations via the empty circle property, whereby a triangulation of a set of sites is Delaunay if the circumcircle of none of its triangles contains sites in its interior.
- QUOTE: A Voronoi diagram induced by a finite set A of sites is a decomposition of the plane into possibly unbounded (convex) polygons called Voronoi regions, each consisting of those points at least as close to some particular site as to the others.
2001
- (Luo & Hancock, 2001) ⇒ Bin Luo and Edwin R. Hancock. (2001). “Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10).
- Abstract: This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is, it uses only the edge or connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions: 1) commencing from a probability distribution for matching errors, we show how the problem of graph matching can be posed as maximum-likelihood estimation using the apparatus of the EM algorithm; and 2) we cast the recovery of correspondence matches between the graph nodes in a matrix framework. This allows one to efficiently recover correspondence matches using the singular value decomposition. We experiment with the method on both real-world and synthetic data. Here, we demonstrate that the method offers comparable performance to more computationally demanding methods.
1980
- (Lee and Schachter, 1980) Lee, D. T., & Schachter, B. J. (1980). Two algorithms for constructing a Delaunay triangulation. International Journal of Computer & Information Sciences, 9(3), 219-242.
- Abstract: This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set of N points. The first algorithm uses a divide-and-conquer approach. It runs in O(NlogN) time, which is asymptotically optimal. The second algorithm is iterative and requires O(N2) time in the worst case. However, its average case performance is comparable to that of the first algorithm.
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