Talk:Euclidean minimum spanning tree

From Wikipedia, the free encyclopedia

Contents 1 Realization problem for EMST 2 Broken 3 is it an open problem? 4 Not expected time?

[edit] Realization problem for EMST

Added a more mathematically precise definition in the misc section. I found the way it was written to be confusing without the mathematical definition written out. —Preceding unsigned comment added by 129.97.152.70 (talk) 18:18, 25 September 2007 (UTC)

[edit] Broken

Apparently you cannot link to an outside website from within an image tag or whatever the hell you call those things. I removed it to preserve the caption and pointed the Leda back at wikipedia. I saw some talk on the image page about Dcoetzee asking about using the image and asking about linking to the Leda website so if I'm breaking some sort of prior agreement let me know. Wjw 20:11, 23 Dec 2004 (UTC)

I turned it into a reference to the external links section. That should do the trick. Deco 07:54, 26 Dec 2004 (UTC)

[edit] is it an open problem?

Please note in your passage if it's still an open problem in computational geometry or not. Thanks.

Okay. Dcoetzee 06:03, 14 July 2007 (UTC)

[edit] Not expected time?

I reverted the prior edits because I'm not aware of any determinstic O(n log n) algorithm for computing Delaunay triangulations. Has this problem been derandomized? If so could you provide a reference? Or are you describing a different algorithm? Please explain. Dcoetzee 10:24, 14 July 2007 (UTC)

Most of them are deterministic. Fortune's beach-line plane-sweep (as described e.g. in the yellow book) would be a perfectly good example. It constructs the Voronoi diagram rather than the Delaunay triangulation but that's unimportant since the two are so closely related. —David Eppstein 17:13, 14 July 2007 (UTC)

It would be a good idea not only write wikipedia, but also read wikipedia. The Delaunay triangulation article, linked from the description of the example EMST algorithm, actually descibes deterministic algorithms. P.S. This is not just grumbling; this is what I usually do, because in this way I do "two in one", I both double-check facts and possibly fill in the gaps in surrounding articles. `'Míkka 19:14, 14 July 2007 (UTC)

Apologies - I had not reviewed it recently. It does in fact describe such a solution (and indeed as you added, an even faster randomized algorithm). I apologize for assuming that the edits were made in error. Dcoetzee 19:49, 14 July 2007 (UTC)