Talk:Delaunay triangulation/Archive 1

This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

The Mactutor biographies list Boris Nikolaevich Delone at [1] without saying anything about triangulations, and Georgy Fedoseevich Voronoy without mentioning

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)

"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 http://en.wikipedia.org/w/index.php?title=Delaunay_triangulation&oldid=7628612 Bhudson 19:31, 8 December 2006 (UTC)

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)

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)

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

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 75.144.21.201 (talk) 21:35, 13 May 2009 (UTC)

The description of the incremental algorithm remains sketchy, now even after 10 years since a better description was requested. Someone know how to fix this, please? — Preceding unsigned comment added by 87.100.188.42 (talk) 18:05, 7 November 2019 (UTC)

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. --84.167.187.231 (talk) 12:32, 12 January 2009 (UTC)

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)

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)

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 88.73.236.118 (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)

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 203.187.204.231 (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)

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)

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)

"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 180.149.51.68 (talk) 11:15, 28 October 2013 (UTC)

Seriously, this is not a common or intuitively understood thing (at least if you aren't a native speaker) — Preceding unsigned comment added by 81.217.141.156 (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)

In the Algorithms section, the last determinant simplification skips a step. When I was first examining the simplification I noticed that ${\displaystyle (A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})}$ (middle matrix) was simplified to ${\displaystyle (A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}}$ (final matrix).

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 ${\displaystyle {A-D,B-D,C-D}}$ To verify this assumption, I wrote the follow code to test the equivalency of the first and last matrix:

Test Code

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.

"""
    Short program to test determinant calculations written on
    https://en.wikipedia.org/wiki/Delaunay_triangulation#Algorithms
    Tested using Python 3.5, but should work on 2.6+

    pip3 install numpy
"""
from __future__ import print_function

import numpy as np

# backwards compatability
try:
    xrange
except NameError:
    xrange = range

def primary_det(A, B, C, D):
    """return the first determinant calculation"""
    return np.linalg.det(
        np.matrix([
            [A[0], A[1], A[0] * A[0] + A[1] * A[1], 1],
            [B[0], B[1], B[0] * B[0] + B[1] * B[1], 1],
            [C[0], C[1], C[0] * C[0] + C[1] * C[1], 1],
            [D[0], D[1], D[0] * D[0] + D[1] * D[1], 1],
        ])
    )

def simplified_det(A, B, C, D):
    """return the last (simplified) determinant"""
    A_2 = A - D
    B_2 = B - D
    C_2 = C - D
    return np.linalg.det(
        np.matrix([
            [A_2[0], A_2[1], A_2[0] * A_2[0] + A_2[1] * A_2[1]],
            [B_2[0], B_2[1], B_2[0] * B_2[0] + B_2[1] * B_2[1]],
            [C_2[0], C_2[1], C_2[0] * C_2[0] + C_2[1] * C_2[1]],
        ])
    )

def main():
    """test the determinants against each other for validation"""

    # Test Triangle IN COUNTERCLOCKWISE ORDER!!!
    v1 = np.array([0, 0])
    v2 = np.array([24, -2])
    v3 = np.array([-5, 42])

    # center point
    center = np.array([(v1[0] + v2[0] + v3[0]) / 3, (v1[1] + v2[1] + v3[1]) / 3])

    # Use polar coordinates to generate test points
    for radius in np.arange(0.0, 90.0, 0.0625):
        for theta in xrange(0, 360, 1):
            testp = np.array([theta, theta])
            testp = testp * np.pi / 180 # to radians
            testp = np.array([np.cos(testp[0]), np.sin(testp[1])]) # to cartesian
            testp = testp * radius # scaleby radius
            testp = testp + center # center from triangle

            p_det = primary_det(v1, v2, v3, testp)
            s_det = simplified_det(v1, v2, v3, testp)

            if abs(p_det - s_det) > 0.001: # epsilon
                print(str(p_det) + " != " + str(s_det))
                print("Simplification is not valid")
                exit()

    print("Failed to disprove simplification")

if __name__ == "__main__":
    # execute only if run as a script
    main()

Conclusion

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.

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 (talk • contribs) 15:25, 23 August 2018 (UTC)

Which of the given algorithms is suitable if the points are not on a plane but on the surface of a sphere? Or do special algorithms exist for this case? --RokerHRO (talk) 16:16, 22 December 2018 (UTC)

For points on a sphere, the 2d Delaunay triangulation and the 3d convex hull are more or less the same thing as each other. You can solve it directly, or it's equivalent by polar projection to a Delaunay triangulation problem on the Euclidean plane (K.Q. Brown, "Voronoi diagrams from convex hulls", Inf. Proc. Lett. 1979). —David Eppstein (talk) 17:56, 22 December 2018 (UTC)

Thank you for you quick answer. :-)

I asked because I'd like to see the answer to my questions in the article, because I think I am not the only one with that problem/question. So it would be nice if the article would explain the solution in a comprehensive way. What do you think? --RokerHRO (talk) 22:48, 22 December 2018 (UTC)

It would be reasonable to explain both the connection between 2d Delaunay triangulations and 3d convex hulls, and the definition of Delaunay triangulations in non-Euclidean geometries, in both cases based on published sources. But "explain the solution in a comprehensive way" seems to lean towards

WP:NOTHOWTO. —David Eppstein (talk

) 23:16, 22 December 2018 (UTC)

I think, a short sentence like: "According to SOURCE points on a sphere surface can be triangulated by transforming the dataset via THIS into a THAT and triangulate the result with ALGORITHM." is not a Howto but a useful and sensible information. --RokerHRO (talk) 12:52, 14 January 2019 (UTC)

The "see also" section contains a reference to Pisot-Vijaraghavan numbers. Whilst a quick search indicates that the latter have relevance to some quasiperiodic point sets which might have interesting Delaunay triangulations, this connection seems a bit tenuous to me - can anyone help by making a reference to PV in the DT article or vice versa, or perhaps delete the "see also" reference? Carl P Dettmann (talk) 09:00, 16 May 2019 (UTC)

This article states that B. Delaunay did his work on the subject and published it in form of an article "Sur la sphère vide" in 1934. However, I found that "Sur la sphère vide" was actually given as an invited talk already 10 years earlier at the International Congress of Mathematicians in Toronto, Canada, 1924, where it was also published first in the form of proceedings. Should this be updated both in the first paragraph and the references? If nobody protests I would at this at some point. --Sethur2 (talk) 13:00, 6 November 2019 (UTC)

Update: I found the corresponding proceedings, the article is on page 695 (or 719 in abs. numbers): https://www.mathunion.org/fileadmin/ICM/Proceedings/ICM1924.1/ICM1924.1.ocr.pdf --Sethur2 (talk) 13:12, 6 November 2019 (UTC)

@

Constrained Delaunay triangulation is a too-short article on an obviously-notable subject (over 5000 hits on Google Scholar); why not expand it? Being a stub is not a valid reason for effective deletion. Merging it here means that it is permanently a stubby part of a larger article rather than having room to grow properly. And although this article wouldn't be too badly damaged and brought off-topic by the constrained material (in its current length), the refinement material you also merged is a very different story. —David Eppstein (talk) 05:57, 23 February 2021 (UTC)

It's actually the opposite intention: merging constrained DT here will bring more attention to it, making it more likely that it'll grow. And if it does (which I doubt), then it can be split off when it reaches fruition. It's been a stub for a decade, I want to try something different. Glad that you don't find it damaging.

fgnievinski (talk

) 06:16, 23 February 2021 (UTC)

Doesn't mean I think it's a good idea, though. My personal experience is that having topics covered only as subtopics of parent articles, rather than as separate articles, is that it discourages me (and I assume other readers) from forking them off again, or even noticing the problem that we have a missing article on a notable topic. I don't see why you think that making the topic shrink into a small paragraph or two of a larger article, instead of its own separate article would paradoxically make it more prominent and make it grow. If anything, growth of that subtopic here is likely to cause editors to think it unbalances this article and cut it down again. —David Eppstein (talk) 06:50, 23 February 2021 (UTC)

Now on to the DT refinement articles, there are two articles about specific methods but no article about DT refinement per se. I understand your point that it might be too much detail for the present article. So how about merging the two methods into a new article about

I have no objection to that merge, as I think those two articles are indeed overly specific for Wikipedia. However, the phrase by which this topic is generally known is "Delaunay refinement" without the middle word. Again, thousands of hits on Google scholar. Be sure to do enough reading to understand the big picture of the topic and how these subtopics fit into it in performing a merge, rather than thinking you can get something meaningful by merely mechanically cutting and pasting pieces of articles together. Your use of a nonstandard phrase as the proposed title for this topic is not giving me great confidence that you're already familiar enough with it to do justice to a merge. —David Eppstein (talk) 06:50, 23 February 2021 (UTC)

I believe in incremental improvements; leaving the articles alone ain't an improvement.

fgnievinski (talk

) 07:20, 23 February 2021 (UTC)

Slashing up things with no understanding of them and thinking the pile of confetti you've left on the floor is an article ain't either. —David Eppstein (talk)

stub article describing straightforward generalization of main concept

Again, no. It's an important and separate topic. As I already said above, there are 5000 sources on Google scholar that can be used to support it. It is not even correct to say that it's a generalization, because the main concept of Delaunay triangulations is not dimension-specific and constrained Delaunay mainly works in 2d. And being a stub is a stupid reason for trying to get rid of stuff. fgnievinski has demonstrated in recent edits a clear lack of understanding of these topics and a tendentious refusal to take the time to learn about them before making big changes based on superficial readings of our articles, so I don't see why fgnievinski's continued efforts to do the same thing should be taken seriously rather than sanctioned as tendentious editing. —David Eppstein (talk) 18:04, 23 February 2021 (UTC)

Dear @

fgnievinski (talk

) 18:13, 23 February 2021 (UTC)

Presenting your bad ideas in article space is neither necessary nor sufficient for encouraging discussion here. As for OWNBEHAVIOR: Yes, I feel protective of the encyclopedia against the rampages of editors who don't know what they're doing and think running around slapping unrelated topics together improves things. If your edits were more constructive you wouldn't have encountered that. —David Eppstein (talk) 18:22, 23 February 2021 (UTC)