Talk:Delaunay triangulation

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Low Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 00:28, 2 June 2007 (UTC)

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)

[edit] What is sweepline?

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

[edit] Triangularization?

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)

[edit] Incremental triangulation using a triangulation history tree?

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.

[edit] Duality

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)

[edit] bad image

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)

[edit] Latest changes

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)