Euclidean minimum spanning tree

Each edge lies in an empty region of the plane, and these regions can be used to prove that the Euclidean minimum spanning tree is a subgraph of other geometric graphs including the relative neighborhood graph and Delaunay triangulation.

This is optimal in some models of computation, although faster randomized algorithms exist for points with integer coordinates.

For points in higher dimensions, finding an optimal algorithm remains an open problem.

[3] Publications on the Euclidean minimum spanning tree commonly abbreviate it as "EMST".

[8] When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".

[9][10][11] Several other standard geometric networks are closely related to the Euclidean minimum spanning tree: Whenever two edges of a Euclidean minimum spanning tree meet at a vertex, they must form an angle of 60° or more, with equality only when they form two sides of an equilateral triangle.

[16] For points generated at random from a given continuous distribution, the minimum spanning tree is almost surely unique.

However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.

of any Euclidean minimum spanning tree, the lens (or vesica piscis) formed by intersecting the two circles with

[12] Certain geometric graphs have definitions involving empty regions in point sets, from which it follows that they contain every edge that can be part of a Euclidean minimum spanning tree.

points in the unit square (or any other fixed shape), the total length of the minimum spanning tree edges is

[22] The same bound applies to the expected total length of the minimum spanning tree for

[12] Another interpretation of these results is that the average edge length for any set of points in a unit square is

However, in the random case, with high probability the longest edge has length approximately

[24] Any geometric spanner, a subgraph of a complete geometric graph whose shortest paths approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points.

Repeating this subdivision process allows a Euclidean minimum spanning tree to be subdivided arbitrarily finely.

on complete graphs, unlike another common choice, Kruskal's algorithm, which is slower because it involves sorting all distances.

[20] A faster approach to finding the minimum spanning tree of planar points uses the property that it is a subgraph of the Delaunay triangulation: The result is an algorithm taking

[26] Additionally, since the Delaunay triangulation is a planar graph, its minimum spanning tree can be found in linear time by a variant of Borůvka's algorithm that removes all but the cheapest edge between each pair of components after each stage of the algorithm.

[26] In the other direction, the Delaunay triangulation can be constructed from the minimum spanning tree in the near-linear time bound

In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the convex hull into

—faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms.

In the bichromatic closest pair problem, the input is a set of points, given two different colors (say, red and blue).

[4][11] For uniformly random point sets in any bounded dimension, the Yao graph[20] 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.

[33] The Euclidean minimum spanning tree has been generalized in many different ways to systems of moving or changing points: An asymptotic lower bound of

of the Euclidean minimum spanning tree problem can be established in restricted models of computation.

[26] 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 southern Moravia,[47] and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger.

[5] 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.

More generally, similar methods can recognize curves drawn in a dotted or dashed style rather than as a single connected set.

Euclidean minimum spanning tree of 25 random points in the plane
Twelve unit spheres all tangent to a central unit sphere. The minimum spanning tree of their 13 center points has degree 12 at the central point.
Empty regions for the Euclidean minimum spanning tree: For the red edge shown, these regions cannot contain any other vertices of the tree. White: the empty lens defining the relative neighborhood graph . Light blue: the diameter circle defining the Gabriel graph and forming an empty circle for the Delaunay triangulation . Dark blue: a 60°–120° rhombus that cannot overlap with the rhombi of other spanning tree edges.