Talk:Delaunay triangulation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field:  Discrete mathematics

The Mactutor biographies list Boris Nikolaevich Delone at [1] without saying anything about triangulations, and Georgy Fedoseevich Voronoy without mentioning Voronoi tesselations. Can someone confirm that that Delone is the same person who is mentioned in this article? Also, is this the same Delaunay whose name is inscribed on the Eifel Tower alongside Fourier and Cauchy and 69 others? Michael Hardy 23:09, 14 Dec 2004 (UTC)

Yes (same Delone), yes (same Voronoy), and maybe (Eiffel Tower). According to V.A.Zalgaller, B.N. himself spelled his last name as Delaunay. Back during the times (pre-WWII) when the Soviet abstracts were published in French as opposed to English, this was the official Soviet publications spelling as well. OTOH, the math genealogy lists him as Delone (probably due to Mactutor). I can point you at least one SCREAMING inaccuracy at Mactutor's wrt another person --- Vinogradov. Mactutor re-published the common Soviet lie (originating in Vinogradov-edited math journals) that V. was the director of the Steklov institute until his death, not mentioning the period when Sobolev was the director. This despite the fact that the same Mactutor mentions the directorship on the Sobolev page! Both bios are signed by the same 2 authors. No wonder they're also inconsistent with respect to transliteration spellings (or am I instilling guilt by association here? caveat emptor...) Whatever the origins, I am proud to have removed the corresponding inaccuracy from the WP. BACbKA 23:38, 14 Dec 2004 (UTC)
BND has his name used both as Delaunay for his triangulation work and Delone for work I'm not familiar with that is closer to statistics -- Ken Clarkson has a talk slide with both transliterations appearing on it. I don't think it's a communist conspiracy. Bhudson 19:19, 8 December 2006 (UTC)
No to Eiffel Tower. It was astronomer Charles-Eugène Delaunay. The rest of BACbKA is agreed, even without Zalgaller, see the reference from Soviet math journal in the article. Mikkalai 00:42, 15 Dec 2004 (UTC)

Sorry about my dumb question about the Eiffel Tower. Since he was not born until after the tower was built, obviously it's not the same person. Someone has suggested in an email that the one on the Eiffel Tower may have been an ancestor of this Delaunay. Michael Hardy 03:05, 15 Dec 2004 (UTC)

What is sweepline?[edit]

"A common way to speed up this method is to sort the vertices by the first coordinate, and add them in that order."

Sorting the vertices by the first coordinate produces a sequence of vertices that would result if a line were swept over them. (Yes, you're probably thinking of Lumines by now.) This sorting method has O(n log n) performance, and so does "sweepline", which the article doesn't describe. So does "sweepline" just refer to one of the incremental algorithms? --Damian Yerrick 20:51, 14 August 2005 (UTC)

UPDATE: I found a reference, and yes, those are the same. --Damian Yerrick () 05:30, 1 January 2007 (UTC)


I've never heard the term "Delone triangularization" before this page, and neither has Google (though there are loads of copies of this wikipedia article. Can someone confirm its existence? It was added in Bhudson 19:31, 8 December 2006 (UTC)

Incremental triangulation using a triangulation history tree?[edit]

The article talks something about incremental O(n log n) algorithm that keeps the triangulation is some sort of tree. More information, the name of the algorithm and a reference would be nice because I couldn't find more about this.

I added some of this. For starters, it's not a tree, it's a DAG, but that doesn't matter much. The de Berg et al book has all the details in excrutiating detail for 2d. A related algorithm eagerly keeps points in their triangle, and that may be cheaper in practice, but morally it's the same thing. Also, it doesn't have the nice textbook explanation. Bhudson (talk) 05:05, 25 June 2008 (UTC)


The notion of duality this article linked to is a bit weird: Duality (projective geometry). Normally the Voronoi and Delaunay are regarded to be graph duals, rather than geometric duals. To become geometric duals you have to go through the intermediary of some kind of lifting map like the parabolic one described later in the article.

The same comment holds true with regards to the Voronoi article. Bhudson 23:07, 8 December 2006 (UTC)

bad image[edit]

In the image at Image:Delaunay circumcircles.png, you can BARELY see the circles. Can it be replaced by a better one? Michael Hardy 02:32, 9 November 2007 (UTC)

Latest changes[edit]

The introduction is mathematically accurate but from my engineer's viewpoint is overcomplex, that's why I've added the Delaunay condition section, which is absolutely more clear and easier to understand to anybody out of the hardcore mathematicians' world. This section is based on the original paper, and so it is referenced.

I'd even suggest placing the Delaunay condition section as the introduction and moving the current overcomplex introduction to a section like "n-dimensional Delaunay tessellation" (triangulation is by definition bidimensional).

Start simple, end complex. Please discuss before changing anything else! Gallando 11:14, 9 November 2007 (UTC)

I've already changed the introduction, it looks so much more readable now! I moved the n-dimensional case to its own section for the sake of clarity (plus: triangulation is by definition 2D, if it can be generalized to n-dimensions, let it be in its own section). Gallando 11:44, 9 November 2007 (UTC)

Agreed. `'Míkka>t 20:44, 9 November 2007 (UTC)
You keep deleting the initial image with the circumcircle, I do think it is clearer to anybody because they can visualize the explanation of the triangle with the three vertices from the point set and the empty circumcircle around it.
If it is useless for you, good for you, but it is absolutely selfish to deny it to others which would like that visual help. Is it that hard for you to leave more information in an article to let more people understand it? I strongly disagree with your absurd continuous removal of that image
BTW: You always complain to others about changing without discussing, what about you behaving as you ask others?!
Gallando 02:08, 10 November 2007 (UTC)

Who thinks that this image is a useful visual clue to insert in the initial definition to help non-mathematicians? I DO
If the three vertices A, B, C that form the triangle ABC are the only ones, in the point set, contained in the circumference, then it meets the Delaunay condition.
Gallando 01:36, 12 November 2007 (UTC)
To be honest I also find the image needlessly complex. Does it matter that the triangle sides are perpendicular to the radius segments? Do the triangle angles need to be labelled when they're not referred to anywhere? Does the centre of the circle need to be labelled or referred to? And it does nothing to indicate that the circumcircle doesn't contain other points. A simple triangle inscribed in a circle is enough. Dcoetzee 05:11, 12 November 2007 (UTC)


I'm not familiar with this algorithm, it's slower than the usual algorithms including Fortune's sweepline algorithm, and the reference appears to have been a broken link. So I removed it while rewriting the incremental algorithm description (which still needs work). Bhudson (talk) 04:57, 25 June 2008 (UTC)

The incremental algorithm excludes the case where the new point lies outside the convex hull of the current point set. This requires adding an unknown number of triangles depending on how many points on the convex hull are visible from the new point. What is the best way to do the adds and flips? Will someone add this to the page? —Preceding unsigned comment added by (talk) 21:35, 13 May 2009 (UTC)

External References[edit]

I added a new external reference at the first place, it is the VoroGlide reference. VoroGlide is way better than the Voronoi/Delaunay applet (second reference now) because the latter uses a bounding triangle that is visible in the triangulation. I suggest to remove the the Voronoi/Delaunay applet. -- (talk) 12:32, 12 January 2009 (UTC)

Question about existence[edit]

If I have a general graph consisting in a set of points and links among them, can I associate to it a "triangulation" in some sense? I mean, regarding the graph as a Voronoi dual to the former triangulation. If yes, can I do it for any d-dimensional generalization of triangle cells or are there requirements to fulfill? I'd like if someone is able to point me out an answer and eventually a reference. I'm posting this question also in Voroni's lattice page. Omar.zanusso (talk) 10:32, 5 March 2009 (UTC)

Definition of Delaunay Condition[edit]

In the most recent edit, the second paragraph has been changed to:

"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, that is, if no vertices lie in the circles' interiors.[1] (Vertices may lie on the perimeter of any circumcircle.)"

My main objection with this definition is the use of the term "triangle net" which is not defined here, and which I have never heard in this context. (I have not read reference [1] but the term does not appear de Berg et al. [2].) Also, this sentence contains essentially the same content as the first sentence of the article, "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)".

Can we give a short, complete definition of the Delaunay triangulation in the first two paragraphs and eliminate some of the redundancy in the current version. RuppertsAlgorithm (talk) 13:27, 26 July 2010 (UTC)

d-dimensional Delaunay-decomposition in O(d*n^2)[edit]

I think this formulation is more than misleading, since it implies that one can compute the whole Delaunay-Complex in quadratic time. This is imposible, because the number of simplices in each dimension sum up to a bigger order. Furthermore the reference to the CGAL-Implementation is no valid proof for the assumtion that this result is true. Though it is easy to prove that the d-dimensional simplices of a d-dimensional delaunay-complex can be enumerated in O(d*n^2) alone from the knowledge of its vertex set. —Preceding unsigned comment added by (talk) 14:33, 10 September 2010 (UTC)

I think a more accurate general formula would be O((nlogn)^d) sice I read that modern d-dimensional algorithms increase exponentialy with dimension. Am I wrong? --Bigmonachus (talk) 00:43, 24 January 2011 (UTC)

Does anyone know a good reference that discusses the worst case time for d-dimensional Delaunay triangulation? The triangulation has at most O(n^(d/2)) simplices. Using an incremental algorithm, even if every simplex had to be searched and/or modified with every vertex insert, that appears to only require O(n^(d/2+1)) to construct the triangulation. I can't think of a reference on the top of my head since most algorithms and analysis are dedicated to showing O(n log n) behavior over a reasonable set of input rather than emphasizing the worst case behavior. RuppertsAlgorithm (talk) 16:10, 24 January 2011 (UTC)

My preference is to remove the line containing the algorithm running time from this section: we should discuss algorithm complexity in the later sections on algorithms. In the current article, the complexity for computing the d-dimensional Delaunay triangulation is mentioned before that of the two-dimensional case, which seems backwards. RuppertsAlgorithm (talk) 16:10, 24 January 2011 (UTC)

Delaunay Triangulation for 3-Dimention[edit]

Does delauny triangulation for 3-Dimension... provide just Convex-hull of Point Cloud Or Complete surface reconstruction of given points in 3D like this one ????????

for more detailed question go over here —Preceding unsigned comment added by (talk) 09:15, 23 May 2011 (UTC)

Neither. As your last link says, it gives a set of tetrahedra, whose overall convex hull is the same as that of the cloud; the smallest faces of the tetrahedra are candidates for the reconstructed surface. —Tamfang (talk) 16:52, 27 May 2011 (UTC)

Sweephull speed?[edit]

While all other have a big o notation speed, the sweephull algorithm seems to lack this. It only notes that it is quicker than QHull which isn't even mentioned in the algorithm. The details of the algorithm are fine but the rest seems a bit like an advert for the algorithm. Esp. the note that there exist a free implementation of this algorithm linking to a site which actually sells one implementation of this, makes me doubt the objectivity of this section. Could these parts of the sweephull section be improved. I am in favour of removing the free implementation part, but I have no idea of the speed of the algorithm, so I am unable to improve this. --Daramarak (talk) 09:18, 2 March 2012 (UTC)

Also, with all due respect, the paper referenced has not been published in a scientific journal (which is surprising if the method is, as stated, faster than the classical one) and is a bit weak in its developments (also, to my mind, the paper does not meet the usual quality standards with among other things quite a lot of spelling mistakes and strange acknowledgments… ). I am not an expert in DT but I think that it would be good if someone familiar with the field could actually verify and confirm that this algorithm is known, used, and presents some kind of interest. Thibaut Lienart 13:30, 25 April 2012 (UTC)

Flip Algorithms[edit]

Re "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.". BTW, this statement is not true in general, AFAIK. Reason: "edge flip" can correct a non-Delaunay pair of triangles (having a shared edge), but it doesn't help if a point that is NOT in one of the three neighbor triangles of triangle ABC falls within the circumcircle of ABC. That is, suppose D,E,F are neighboring points, with ABD, BCE, CAF being the 3 neighbor triangles of ABC. Another point G can cause ABC to fail Delaunay constraint. In this case, all nearby triangles must be torn down, and reconstructed by some algorithm other than "edge flip" (IMHO)... I ran into this recently, using Poly2Tri (which fails to do a general test of Delaunay violation, it only tests the 3 neighbor triangles. I added logic to check neighbors of neighbors and found a violation causing a visual glitch I was seeing -- fix TBD). ToolmakerSteve (talk) 04:31, 16 March 2012 (UTC)

This criticism is justified in that the article currently doesn't explain correctly why edge flipping works, but not in the conclusion that it doesn't work. See this math.SE answer for a more detailed explanation of why edge flipping works. While it's true that a non-Delaunay triangle can have locally Delauany edges, a triangulation with a non-Delaunay triangle must have an edge that isn't locally Delaunay. Thus edge flipping works not by looking for non-Delaunay triangles and flipping one of their edges, but by looking for edges that aren't locally Delaunay and flipping them. If we agree on this, we should adapt the article accordingly. Joriki (talk) 05:51, 30 April 2012 (UTC)

A correction to property no.3(refer 'Properties' section)[edit]

"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" should be "In the plane (d = 2), if there are b vertices that lie on the boundary of the convex hull, then any triangulation of the points has at most 2n − 2 − b triangles, plus one exterior face".

One can refer chapter 9, theorem 9.1 from the book cited as reference no. 2(in the article itself) for the source of suggested correction. — Preceding unsigned comment added by (talk) 11:15, 28 October 2013 (UTC)

A correction (and question) regarding the last property[edit]

The result in the paper by Keil and Gutwin is specific to dimension d=2. Is there a bound on the stretching factor for higher dimension? Is there a lower bound on the stretching number a function of d? — Preceding unsigned comment added by Yoavfreund (talkcontribs) 15:25, 23 August 2018 (UTC)

What dies "flipping edges" even mean?[edit]

Seriously, this is not a common or intuitively understood thing (at least if you aren't a native speaker) — Preceding unsigned comment added by (talk) 20:24, 30 September 2016 (UTC)

That's why it's defined immediately after its first use. —David Eppstein (talk) 23:18, 30 September 2016 (UTC)

Validating the determinant simplification[edit]

In the Algorithms section, the last determinant simplification skips a step. When I was first examining the simplification I noticed that (middle matrix) was simplified to (final matrix). Binomial expansion shows that these two expressions are not the same.

However, it occurs to me that perhaps the last matrix is not a simplification of the center matrix, but in fact a reconstruction of the first matrix using To verify this assumption, I wrote the follow code to test the equivalency of the first and last matrix:

Test Code[edit]

The code starts from the center of a test triangle and (slowly) spirals out testing both matrices' determinants. It runs in a 2D Cartesian plane.

 1 """
 2     Short program to test determinant calculations written on
 4     Tested using Python 3.5, but should work on 2.6+
 6     pip3 install numpy
 7 """
 8 from __future__ import print_function
10 import numpy as np
12 # backwards compatability
13 try:
14     xrange
15 except NameError:
16     xrange = range
18 def primary_det(A, B, C, D):
19     """return the first determinant calculation"""
20     return np.linalg.det(
21         np.matrix([
22             [A[0], A[1], A[0] * A[0] + A[1] * A[1], 1],
23             [B[0], B[1], B[0] * B[0] + B[1] * B[1], 1],
24             [C[0], C[1], C[0] * C[0] + C[1] * C[1], 1],
25             [D[0], D[1], D[0] * D[0] + D[1] * D[1], 1],
26         ])
27     )
29 def simplified_det(A, B, C, D):
30     """return the last (simplified) determinant"""
31     A_2 = A - D
32     B_2 = B - D
33     C_2 = C - D
34     return np.linalg.det(
35         np.matrix([
36             [A_2[0], A_2[1], A_2[0] * A_2[0] + A_2[1] * A_2[1]],
37             [B_2[0], B_2[1], B_2[0] * B_2[0] + B_2[1] * B_2[1]],
38             [C_2[0], C_2[1], C_2[0] * C_2[0] + C_2[1] * C_2[1]],
39         ])
40     )
42 def main():
43     """test the determinants against each other for validation"""
45     # Test Triangle IN COUNTERCLOCKWISE ORDER!!!
46     v1 = np.array([0, 0])
47     v2 = np.array([24, -2])
48     v3 = np.array([-5, 42])
50     # center point
51     center = np.array([(v1[0] + v2[0] + v3[0]) / 3, (v1[1] + v2[1] + v3[1]) / 3])
53     # Use polar coordinates to generate test points
54     for radius in np.arange(0.0, 90.0, 0.0625):
55         for theta in xrange(0, 360, 1):
56             testp = np.array([theta, theta])
57             testp = testp * np.pi / 180 # to radians
58             testp = np.array([np.cos(testp[0]), np.sin(testp[1])]) # to cartesian
59             testp = testp * radius # scaleby radius
60             testp = testp + center # center from triangle
62             p_det = primary_det(v1, v2, v3, testp)
63             s_det = simplified_det(v1, v2, v3, testp)
65             if abs(p_det - s_det) > 0.001: # epsilon
66                 print(str(p_det) + " != " + str(s_det))
67                 print("Simplification is not valid")
68                 exit()
70     print("Failed to disprove simplification")
72 if __name__ == "__main__":
73     # execute only if run as a script
74     main()


The test program fails to disprove the simplification (Proof by exhaustion). For an actual proof, one would need to compute the determinants with symbols and compare.