Euclidean minimum spanning tree

Euclidean minimum spanning tree of 25 random points in the plane

A Euclidean minimum spanning tree is a minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space. It connects the points by a system of line segments, so that any two points can reach each other along a path through the line segments, and it selects line segments that minimize the sum of the Euclidean distances between directly-connected pairs of points.

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 controlled 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 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, a Euclidean minimum spanning tree for $n$ given planar points may be found in time $O(n\log n)$, as expressed in Big O notation. Faster randomized algorithms are known 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 $n$ 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. It is never helpful to form a closed cycle of line segments (a polygon), because one edge of any cycle could be removed, reducing the length while preserving connectivity. Therefore, any minimum-length connecting set of line segments is a tree, and one can equivalently define a Euclidean minimum spanning tree as a tree of line segments between pairs of the given points, with minimum total length. The given points, and line segments connecting pairs of points, may be represented abstractly as the vertices and edges of a complete graph, with the weight of each edge given by the length of its line segment, and a Euclidean minimum spanning tree is a minimum spanning tree of this weighted graph. A given set of points may have more than one Euclidean minimum spanning tree. For instance, for the vertices of a regular polygon, removing any edge of the polygon produces a minimum spanning tree.

A closely related problem is the Steiner tree problem, which 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 the Steiner tree problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the Euclidean minimum spanning tree. In another related problem, the Euclidean traveling salesperson path problem, the connecting line segments must again start and end at the given points, but with the additional restriction that each point touches at most two of the line segments. Because of this additional restriction, the optimal traveling salesperson path may be longer than the Euclidean minimum spanning tree, but it is at most twice as long. The paths connecting pairs of points in a Euclidean spanning tree may be much longer than the Euclidean distance between the points; geometric spanners connect all pairs of points by short paths, but generally have cycles rather than being trees.

Properties

Angles and vertex degrees

Twelve unit spheres all tangent to a central unit sphere. The Euclidean minimum spanning tree of their 13 center points has degree 12 at the central point.

When any 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 shorter third edge of the triangle they form, leading to a tree with smaller total length. This angle bound contrasts with the angles at vertices in the Steiner tree problem: an optimal Steiner tree has all angles at least 120°.

When a vertex in a tree has all angles at least 60°, one can form a system of non-overlapping unit spheres centered at that vertex and at the points two units away from it along each edge; each of these spheres is tangent to the central sphere. Conversely, when a system of non-overlapping unit spheres are all tangent to a central sphere, the center points of the spheres have a Euclidean minimum spanning tree with edges from each outer center point to the central point. Therefore, the maximum possible degree of a vertex in a Euclidean minimum spanning tree (the number of edges touching that vertex) equals the kissing number, the maximum number of unit spheres that can touch a central unit sphere without crossing it. In particular this means that planar Euclidean minimum spanning trees have maximum degree at most six (or, for points in general position, five) and three-dimensional Euclidean minimum spanning trees have maximum degree at most twelve. Although it is possible for a planar Euclidean minimum spanning tree to have vertices of degree six, every set of points has some minimum spanning tree with maximum degree five.

For points generated at random from a given continuous distribution, the Euclidean minimum spanning tree is almost surely unique. The numbers of vertices of any given degree (if that degree is possible) 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

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.

For any edge $uv$ of any Euclidean minimum spanning tree, the lens (or vesica piscis) formed by intersecting the two circles with $uv$ as radius cannot have any other given point $w$ in its interior. This is because, by the geometry of the two circles, $w$ would be closer to both $u$ and $v$ than they are to each other. If edge $uv$ were removed from the tree, $w$ would remain connected to one of $u$ and $v$, but not the other. Replacing the removed edge $uv$ by $uw$ or $vw$ (whichever of these two edges reconnects $w$ to the vertex from which it was disconnected) would produce a shorter tree, contradicting the minimality of the initial tree. This contradiction shows that $w$ cannot exist. It follows that any other region of the plane within this empty lens must also be empty.

For any edge $uv$ of any Euclidean minimum spanning tree, the rhombus with angles of 60° and 120°, having $uv$ as its long diagonal, is disjoint from the rhombi formed in the same way for all other edges. Two edges that share an endpoint cannot have overlapping rhombi, because that could only happen for edges forming an angle sharper than 60°, and two disjoint edges cannot have overlapping rhombi, because if they did then the longer of the two edges could be replaced by a shorter edge among the same four vertices.

Supergraphs

Certain geometric graphs defined from a system of points using empty regions must contain all edges of all Euclidean minimum spanning trees. These include the following:

• 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:

Euclidean minimum spanning tree ⊆ relative neighborhood graph ⊆ Urquhart graph ⊆ Gabriel graph ⊆ Delaunay triangulation.

Another graph guaranteed to contain the Euclidean 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 can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.

Total length

For $n$ points in the unit square (or any other shape of constant diameter), the total length of the Euclidean minimum spanning tree edges is $O({\sqrt {n}})$. Some sets of points, such as points evenly spaced in a ${\sqrt {n}}\times {\sqrt {n}}$ grid, attain this bound. For points in a unit hypercube in a $d$-dimensional space, the corresponding bound is $O(n^{(d-1)/d})$. The same bound applies to the expected total length of the Euclidean minimum spanning tree for $n$ 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 Euclidean minimum spanning tree is $O(1)$. This bound follows from the property that the edges have disjoint rhombi, with area proportional to the squared edge lengths. The $O({\sqrt {n}})$ bound on total length in turn follows by combining the Cauchy–Schwarz inequality with the bound on squared edge lengths.

Another way of interpreting these results is that the average edge length for points in a unit square is $O(1/{\sqrt {n}})$, 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 $1/{\sqrt {n}}$. However, in the random case, with high probability the longest edge is longer, proportional to ${\sqrt {\log n}}/{\sqrt {n}}$. That is, with high probability, some edges of length proportional to ${\sqrt {\log n}}/{\sqrt {n}}$ are required in a graph that connects all pairs of random points in a unit square. With only shorter edges, these points will remain separated into two or more clusters, formed by removing the longest edge from the spanning tree. The constant of proportionality for this longest edge length, and its distribution around its expected value, are also known.

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 Euclidean minimum spanning tree, and one of the standard quality measures for geometric spanners is the ratio between the total edge length of a spanner and of the Euclidean 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 Euclidean minimum spanning tree and Steiner tree for the same set of points in the plane, is $2/{\sqrt {3}}\approx 1.1547$, 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 the edges of any Euclidean minimum spanning tree to be subdivided arbitrarily finely. However, subdividing some but not all 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

For points in any dimension, the Euclidean minimum spanning tree can be constructed in time $O(n^{2})$ by constructing a complete graph with an edge between every pair of points, weighted by Euclidean distance, and then applying a graph minimum spanning tree algorithm such as the Prim–Dijkstra–Jarník algorithm or Borůvka's algorithm on it. These algorithms can be made to take time $O(n^{2})$ on complete graphs, unlike another common choice, Kruskal's algorithm, which is slower because it involves sorting all distances. For points in low-dimensional spaces, it is possible to solve the problem more quickly, as detailed below.

Computing Euclidean distances involves a square root calculation. In any comparison of edge weights, this calculation can be avoided by comparing the squares of the Euclidean distances instead instead of the distances themselves. Because this change does not affect the outcome of these comparisons, it does not change the result of the minimum spanning tree computation. As well as speeding up the calculation by avoiding a step, this allows the construction of a minimum spanning tree for points with integer coordinates to be performed exactly using only integer arithmetic.

Two dimensions

A faster approach to finding the Euclidean minimum spanning tree in a plane uses the property that it is a subgraph of the Delaunay triangulation:

1. Compute the Delaunay triangulation, which can be done in $O(n\log n)$ time. Because the Delaunay triangulation is a planar graph, it has at most $3n-6$ edges.
2. Label each edge with its (squared) length.
3. Run a graph minimum spanning tree algorithm on this graph to find a minimum spanning tree. Since there are $O(n)$ edges, this requires $O(n\log n)$ time using any of the standard minimum spanning tree algorithms.

The final result is an algorithm taking $O(n\log n)$ time.

If the input coordinates are integers and can be used as array indices, faster algorithms are possible: the Delaunay triangulation can be constructed by a randomized algorithm in $O(n\log \log n)$ expected time. 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. Therefore, the total expected time for this algorithm is $O(n\log \log n)$.

Higher dimensions

The problem can also be generalized to $n$ points in the $d$-dimensional space $\mathbb {R} ^{d}$. In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the convex hull into $d$-dimensional simplices) contains the minimum spanning tree; however, the triangulation might contain the complete graph. 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 $O(dn^{2})$ time. For three dimensions it is possible to find the minimum spanning tree in time $O{\bigl (}(n\log n)^{4/3}{\bigr )}$, and in any dimension greater than three it is possible to solve it in time

$$O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)$$

for any $\varepsilon >0$, faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms.

The optimal time complexity for higher dimensional Euclidean minimum spanning trees remains unknown, but it is closely related to the time for 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 Euclidean 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 Euclidean minimum spanning tree. By carefully choosing a sequence of colorings of subsets, and finding the bichromatic closest pair of each subproblem, it is possible to find the Euclidean minimum spanning tree 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.

For uniformly random point sets in any bounded dimension, the Yao graph 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. This allows the minimum spanning tree itself to be constructed in linear time, by using a randomized linear time algorithm for graph minimum spanning trees. 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 $O(n\log n)$ time bound, for random inputs or inputs whose distances and clustering resemble those of random data, while exhibiting better performance on real-world data.

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 $O(n\log n)$. The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the Euclidean minimum spanning tree. Using these ideas, it is possible to produce a $(1+\varepsilon )$-approximation in $O(n\log n)$ time, whenever $\varepsilon$ is a constant. More precisely, by choosing each representative pair to be an approximation to the closest pair in its equivalence class, and varying the quality of this approximation carefully for different pairs, the dependence on $\varepsilon$ in the time bound can be given as $O(n\log n+(\varepsilon ^{-2}\log ^{2}{\tfrac {1}{\varepsilon }})n),$ for any fixed dimension.

Lower bound

An asymptotic lower bound of $\Omega (n\log n)$ of the Euclidean minimum spanning tree problem can be established in restricted models of computation, such as the algebraic decision tree and algebraic computation tree models, in which the algorithm has access to the input points only through certain restricted primitives that perform simple algebraic computations on their coordinates: in these models, the closest pair of points problem requires $\Omega (n\log n)$ time, but the closest pair is necessarily an edge of the Euclidean minimum spanning tree, so the Euclidean minimum spanning tree also requires this much time. However, these lower bounds do not apply to models of computation with integer point coordinates, in which bitwise operations and table indexing operations are permitted using those coordinates. In these models, faster algorithms are possible, as described above.

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

Minimum spanning trees are closely related to single-linkage clustering, one of several methods for hierarchical clustering. This correspondence applies to the Euclidean minimum spanning tree, for clustering points in a Euclidean space. The edges of a Euclidean minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Although the long thin cluster shapes produced by single-linkage clustering can be a bad fit for certain types of data, such as 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 halos of galaxies.

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. Similar methods can be used more generally to 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.

Another application of Euclidean minimum spanning trees is a constant-factor approximation algorithm for approximately solving the Euclidean traveling salesman problem, the version of the traveling salesman problem on a set of points in the plane with edges labelled by their length. 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. However, more accurate polynomial time approximation schemes are known for this problem.

Realization

The realization problem for Euclidean minimum spanning trees takes an abstract tree as input, and seeks a geometric location for each vertex of the tree (in a space of some fixed dimension) so that the given tree equals the Euclidean minimum spanning tree of points with these locations. Not every abstract tree has such a realization; for instance, the tree must obey the kissing number bound on the degree of each vertex. Additional restrictions beyond this degree restriction exist; for instance, it is not possible for a planar Euclidean minimum spanning tree to have a degree six vertex that is adjacent to a vertex of degree five or six. Determining whether a two-dimensional realization exists is NP-hard. However, the proof that this problem is hard depends on the fact that degree-six vertices in a tree have a very restricted set of realizations: the neighbors of such a vertex must be placed on the vertices of a regular hexagon centered at that vertex. For trees of maximum degree five, a planar realization always exists. Similarly, for trees of maximum degree ten, a three-dimensional realization always exists. For these realizations, some trees may require a bounding box of exponential size, relative to the length of their shortest edge. Trees of maximum degree four have smaller planar realizations, with a bounding box of polynomial area.

See also

• Rectilinear minimum spanning tree, a minimum spanning tree with distances measured using taxicab geometry

External links

• STANN (Michael Connor, Piyush Kumar and Samidh Chatterjee): A C++ library that can compute Euclidean Minimum Spanning Trees in low dimensions