Editing Euclidean minimum spanning tree (section)

===Higher dimensions===
The problem can also be generalized to <math>n</math> points in the <math>d</math>-dimensional space <math>\R^d</math>. In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the [[convex hull]] into <math>d</math>-dimensional [[simplex|simplices]]) contains the minimum spanning tree; however, the triangulation might contain the complete graph.{{r|aesw}} Therefore, finding the Euclidean minimum spanning tree as a spanning tree of the complete graph or as a spanning tree of the Delaunay triangulation both take <math>O(dn^2)</math> time. For three dimensions the minimum spanning tree can be found in time <math>O\bigl((n\log n)^{4/3}\bigr)</math>, and in any greater dimension, in time
<math display=block>O\left(n^{2-\frac{2}{\lceil d/2\rceil+1}+\varepsilon}\right)</math>
for any <math>\varepsilon>0</math>—faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms.{{r|aesw}}

The optimal time complexity for higher-dimensional minimum spanning trees remains unknown,{{r|topp}} but is closely related to the complexity of computing ''bichromatic closest pairs''. In the bichromatic closest pair problem, the input is a set of points, given two different colors (say, red and blue). The output is a pair of a red point and a blue point with the minimum possible distance. This pair always forms one of the edges in the minimum spanning tree. Therefore, the bichromatic closest pair problem can be solved in the amount of time that it takes to construct a minimum spanning tree and scan its edges for the shortest red–blue edge. Conversely, for any red–blue coloring of any subset of a given set of points, the bichromatic closest pair produces one edge of the minimum spanning tree of the subset. By carefully choosing a sequence of colorings of subsets, and finding the bichromatic closest pair of each subproblem, the minimum spanning tree may be found in time proportional to the optimal time for finding bichromatic closest pairs for the same number of points, whatever that optimal time turns out to be.{{r|aesw|kln}}

For uniformly random point sets in any bounded dimension, the [[Yao graph]]{{r|yao82}} or Delaunay triangulation have linear expected numbers of edges, are guaranteed to contain the minimum spanning tree, and can be constructed in linear expected time.{{r|bwy|clarkson|dwyer}} From these graphs, the minimum spanning tree itself may be constructed in linear time, by using a [[Expected linear time MST algorithm|randomized linear time algorithm for graph minimum spanning trees]].{{r|kkt}} However, the poor performance of these methods on inputs coming from clustered data has led [[algorithm engineering]] researchers to develop methods with a somewhat slower <math>O(n\log n)</math> time bound, for random inputs or inputs whose distances and clustering resemble those of random data, while exhibiting better performance on real-world data.{{r|nzz|cck|mrg}}

A [[well-separated pair decomposition]] is a family of pairs of subsets of the given points, so that every pair of points belong to one of these pairs of subsets, and so that all pairs of points coming from the same pair of subsets have approximately the same length. It is possible to find a well-separated pair decomposition with a linear number of subsets, and a representative pair of points for each subset, in time <math>O(n\log n)</math>. The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the minimum spanning tree. Using these ideas, a <math>(1+\varepsilon)</math>-approximation to the minimum spanning tree may be found in <math>O(n\log n)</math> time, for constant <math>\varepsilon</math>. More precisely, by choosing each representative pair to approximate the closest pair in its equivalence class, and carefully varying the quality of this approximation for different pairs, the dependence on <math>\varepsilon</math> in the time bound can be given as <math>O(n \log n + (\varepsilon^{-2} \log ^2 \tfrac{1}{\varepsilon})n),</math> for any fixed dimension.{{r|arymou}}