Editing Euclidean minimum spanning tree (section)

== Applications ==
An obvious application of Euclidean minimum spanning trees is to find the cheapest network of wires or pipes to connect a set of places, assuming the links cost a fixed amount per unit length. The first publications on minimum spanning trees more generally concerned a geographic version of the problem, involving the design of an [[electrical grid]] for [[South Moravian Region|southern Moravia]],{{r|history}} and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger.{{r|lobwei}}

Minimum spanning trees are closely related to [[single-linkage clustering]], one of several methods for [[hierarchical clustering]]. The edges of a minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Once these edges have been found, by any algorithm, they may be used to construct the single-linkage clustering in time <math>O(n\log n)</math>.{{r|gowros}} Although the long thin cluster shapes produced by single-linkage clustering can be a bad fit for certain types of data, such as [[Mixture model|mixtures of Gaussian distributions]], it can be a good choice in applications where the clusters themselves are expected to have long thin shapes, such as in modeling the [[dark matter halo]]s of [[galaxy|galaxies]].{{r|mrg}} In [[geographic information science]], several researcher groups have used minimum spanning trees of the centroids of buildings to identify meaningful clusters of buildings, for instance by removing edges identified in some other way as inconsistent.{{r|urban}}

Minimum spanning trees have also been used to infer the shape of curves in the plane, given points sampled along the curve. For a smooth curve, sampled more finely than its [[local feature size]], the minimum spanning tree will form a path connecting consecutive points along the curve. More generally, similar methods can recognize curves drawn in a dotted or dashed style rather than as a single connected set. Applications of this curve-finding technique include [[particle physics]], in automatically identifying the tracks left by particles in a [[bubble chamber]].{{r|zahn}} More sophisticated versions of this idea can find curves from a cloud of noisy sample points that roughly follows the curve outline, by using the topology of the spanning tree to guide a [[moving least squares]] method.{{r|lee}}

Another application of minimum spanning trees is a [[constant-factor approximation algorithm]] for the [[Euclidean traveling salesman problem]], the problem of finding the shortest [[polygonalization]] of a point set. Walking around the boundary of the minimum spanning tree can approximate the optimal traveling salesman tour within a factor of two of the optimal length.{{r|shahoe}} However, more accurate [[polynomial time approximation scheme|polynomial-time approximation scheme]]s are known for this problem.{{r|bargot}} In [[wireless ad hoc network]]s, [[Broadcasting (networking)|broadcasting]] messages along paths in a minimum spanning tree can be an accurate approximation to the minimum-energy broadcast routing, which is, again, hard to compute exactly.{{r|wclf|chrvp|fknp|ambuhl}}