Talk:Euclidean minimum spanning tree

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)

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)

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)

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)

What about algorithms for higher dimensions? The article refers to [4] which gives the claimed runtimes in expectation, as far as I can see. (The randomization is due to the randomized algorithm for bichromatic closest pair -- maybe that problem was solved faster deterministically? Then maybe that result should be cited too?) Kotya3d (talk) 20:14, 21 June 2024 (UTC)

It's deterministic, but verifying this is a little messy. Reference [4] is indeed a randomized expected time bound. As I state in footnote 1 of my recent paper doi:10.1137/1.9781611977066.6 / arXiv:2110.06163, "in later related work such as [Agarwal & Matoušek, "Dynamic half-space range reporting and its applications", doi:10.1007/BF01293483] they observe that the need for randomness can be eliminated using techniques from [Matoušek, "Approximations and optimal geometric divide-and-conquer", doi:10.1006/jcss.1995.1018]." (references expanded out from original quotation). —David Eppstein (talk) 20:30, 21 June 2024 (UTC)

Thank you! This presumably applies also to the latest improvements (shaving off the polylog for 3D and eps for highD) in the runtime, so perhaps the article may be updated with the improved runtimes; see Chan, Timothy M., and Da Wei Zheng. "Hopcroft’s problem, log-star shaving, 2D fractional cascading, and decision trees." ACM Transactions on Algorithms (2022). Kotya3d (talk) 11:44, 23 June 2024 (UTC)

O(dn²)?

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 n²). Justin W Smith ^talk/_stalk 18:21, 13 May 2010 (UTC)

When talking about a fixed dimension (two or three, say) d is a constant and can be omitted from the bound. Or you could say that it takes O(n²) time for any constant d. But you'd have to be explicit that d is a constant in that case. The O(dn²) bound is valid even for variable values of d: there are O(n²) edges in the complete graph and computing their (squared) lengths takes O(d) time each. —David Eppstein (talk) 18:38, 13 May 2010 (UTC)

Yeah, that makes sense. It would be wrong to assume the dimension is constant, especially in this case where it's rather easy to show how it affects the growth rate. It seems, in general, that the dimension is always a factor in the complexity of a geometric algorithm. So, if an algorithm claims to work in arbitrary dimension, the effect of dimension on its time should be reported. Justin W Smith ^talk/_stalk 19:54, 13 May 2010 (UTC)

Flawed Logic

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)

The logic is not flawed. Here's an algorithm for finding the closest pair of points, assuming you know how to compute the EMST:

1. Compute the EMST
2. Compare the lengths of its n − 1 edges to find the shortest one.

Obviously, if the EMST can be constructed in time T(n), then this algorithm would take time T(n) + O(n). But since we know that (in these models of computation) the fastest possible time bound for finding closest pairs is Θ(n log n), the n log n part of the algorithm must be in the T(n), and the EMST must also take time Ω(n log n). —David Eppstein (talk) 02:51, 10 November 2011 (UTC)

Dual-tree Boruvka algorithm

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