Euclidean minimum spanning tree has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. | ||||||||||
| ||||||||||
A fact from this article appeared on Wikipedia's Main Page in the "Did you know?" column on September 25, 2022. The text of the entry was: Did you know ... that physical applications of Euclidean minimum spanning trees range in scale from the particles in bubble chambers to the dark matter halos of galaxies? |
This article is rated GA-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: |
|||||||||||
|
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)
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)
Please note in your passage if it's still an open problem in computational geometry or not. Thanks.
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)
When specifying the growth rate of geometric algorithms isn't it typical to *not* include the dimension of space in the bound? (I don't remember seeing the d included other places, but perhaps that's because in most cases the dimension does not significantly affect the growth.) The complexity of interest is usually the growth rate with respect to "n", with "d" being considered constant. I ask because I noticed that the time complexity of the Delaunay triangulation is given as O(d n2). Justin W Smith talk/stalk 18:21, 13 May 2010 (UTC)
I quote from the article: "in these models, the closest pair of points problem requires Ω(n log n) time, but the closest pair is necessarily an edge of the EMST, so the EMST also requires this much time." The conclusion here is correct, but the logic is wrong. Simply because the EMST contains the closest pair of points does not mean the closest pair of points must be found, or even than finding the EMST allows you to find the closest pair of points. We cannot immediately conclude that finding the EMST requires at least as much time as finding the closest pair of points. 140.180.55.219 (talk) 01:39, 10 November 2011 (UTC)
I don't see any mention of the dual-tree Boruvka algorithm from March, Ram, and Gray (2010). They claim almost n log n time.
Even nicer, there is code for it available here. http://mlpack.org/docs/mlpack-2.2.5/doxygen/emst_tutorial.html