A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
The edges of the minimum spanning tree meet at angles of at least 60°, at most six to a vertex. In higher dimensions, the number of edges per vertex is bounded by the kissing number of tangent unit spheres. The total length of the edges, for points in a unit square, is at most proportional to the square root of the number of points. 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. By constructing the Delaunay triangulation and then applying a graph minimum spanning tree algorithm, the minimum spanning tree of given planar points may be found in time , as expressed in big O notation. 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.
Definition and related problems A Euclidean minimum spanning tree, for a set of points in the Euclidean plane or Euclidean space, is a system of line segments, having only the given points as their endpoints, whose union includes all of the points in a connected set, and which has the minimum possible total length of any such system. Such a network cannot contain a polygonal ring of segments; if one existed, the network could be shortened by removing an edge of the polygon. Therefore, the minimum-length network forms a tree. This observation leads to the equivalent definition that a Euclidean minimum spanning tree is a tree of line segments between pairs of the given points, of minimum total length. The same tree may also be described as a minimum spanning tree of a weighted complete graph, having the given points as its vertices and the distances between points as edge weights. The same points may have more than one minimum spanning tree. For instance, for the vertices of a regular polygon, removing any edge of the polygon produces a minimum spanning tree.
Publications on the Euclidean minimum spanning tree commonly abbreviate it as "EMST". They may also be called "geometric minimum spanning trees", but that term may be used more generally for geometric spaces with non-Euclidean distances, such as spaces. When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".
Several other standard geometric networks are closely related to the Euclidean minimum spanning tree: The Steiner tree problem again seeks a system of line segments connecting all given points, but without requiring the segments to start and end only at given points. In this problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the minimum spanning tree. In the Euclidean traveling salesperson path problem, the connecting line segments must start and end at the given points, like the spanning tree and unlike the Steiner tree; additionally, each point can touch at most two line segments, so the result forms a polygonal chain. Because of this restriction, the optimal path may be longer than the Euclidean minimum spanning tree, but is at most twice as long. Geometric spanners are low-weight networks that, like the minimum spanning tree, connect all of the points. Unlike the minimum spanning tree, all of these connecting paths are required to be short, having length proportional to the distance between the points they connect. To achieve this property, these networks generally have cycles and so are not trees.
Properties Angles and vertex degrees
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. This is because, for two edges forming any sharper angle, one of the two edges could be replaced by the third, shorter edge of the triangle they form, forming a tree with smaller total length. In comparison, the Steiner tree problem has a stronger angle bound: an optimal Steiner tree has all angles at least 120°.
The same 60° angle bound also occurs in the kissing number problem, of finding the maximum number of unit spheres in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a star, with the central point adjacent to all other points. Conversely, for any vertex of any minimum spanning tree, one can construct non-overlapping unit spheres centered at and at points two units along each of its edges, with a tangency for each neighbor of . Therefore, in -dimensional space the maximum possible degree of a vertex (the number of spanning tree edges connected to it) equals the kissing number of spheres in dimensions. Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five. Three-dimensional minimum spanning trees have degree at most twelve. The only higher dimensions in which the exact value of the kissing number is known are four, eight, and 24 dimensions.
For points generated at random from a given continuous distribution, the minimum spanning tree is almost surely unique. The numbers of vertices of any given degree converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. 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.
Empty regions
For any edge of any Euclidean minimum spanning tree, the lens (or vesica piscis) formed by intersecting the two circles with as their radii cannot have any other given vertex in its interior. Put another way, if any tree has an edge whose lens contains a third point , then it is not of minimum length. For, by the geometry of the two circles, would be closer to both and than they are to each other. If edge were removed from the tree, would remain connected to one of and , but not the other. Replacing the removed edge by or (whichever of these two edges reconnects to the vertex from which it was disconnected) would produce a shorter tree.
For any edge of any Euclidean minimum spanning tree, the rhombus with angles of 60° and 120°, having as its long diagonal, is disjoint from the rhombi formed analogously by all other edges. Two edges sharing an endpoint cannot have overlapping rhombi, because that would imply an edge angle sharper than 60°, and two disjoint edges cannot have overlapping rhombi; if they did, the longer of the two edges could be replaced by a shorter edge among the same four vertices.
Supergraphs 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. These include: The relative neighborhood graph, which has an edge between any pair of points whenever the lens they define is empty. The Gabriel graph, which has an edge between any pair of points whenever the circle having the pair as a diameter is empty. The Delaunay triangulation, which has an edge between any pair of points whenever there exists an empty circle having the pair as a chord. The Urquhart graph, formed from the Delaunay triangulation by removing the longest edge of each triangle. For each remaining edge, the vertices of the Delaunay triangles that use that edge cannot lie within the empty lune of the relative neighborhood graph. Because the empty-region criteria for these graphs are progressively weaker, these graphs form an ordered sequence of subgraphs. That is, using "⊆" to denote the subset relationship among their edges, these graphs have the relations:
Another graph guaranteed to contain the minimum spanning tree is the Yao graph, determined for points in the plane by dividing the plane around each point into six 60° wedges and connecting each point to the nearest neighbor in each wedge. The resulting graph contains the relative neighborhood graph, because two vertices with an empty lens must be the nearest neighbors to each other in their wedges. As with many of the other geometric graphs above, this definition can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.
Total length For points in the unit square (or any other fixed shape), the total length of the minimum spanning tree edges is . Some sets of points, such as points evenly spaced in a grid, attain this bound. For points in a unit hypercube in -dimensional space, the corresponding bound is . The same bound applies to the expected total length of the minimum spanning tree for points chosen uniformly and independently from a unit square or unit hypercube. Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is . This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The bound on total length follows by application of the Cauchy–Schwarz inequality.
Another interpretation of these results is that the average edge length for any set of points in a unit square is , at most proportional to the spacing of points in a regular grid; and that for random points in a unit square the average length is proportional to . However, in the random case, with high probability the longest edge has length approximately longer than the average by a non-constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a Gumbel distribution.
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. Several methods for constructing spanners, such as the greedy geometric spanner, achieve a constant bound for this ratio. It has been conjectured that the Steiner ratio, the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is , the ratio for three points in an equilateral triangle.
Subdivision If every edge of a Euclidean minimum spanning tree is subdivided, by adding a new point at its midpoint, then the resulting tree is still a minimum spanning tree of the augmented point set. Repeating this subdivision process allows a Euclidean minimum spanning tree to be subdivided arbitrarily finely. However, subdividing only some of the edges, or subdividing the edges at points other than the midpoint, may produce a point set for which the subdivided tree is not the minimum spanning tree.
Computational complexity