Euclidean minimum spanning tree

From Wikipedia, the free encyclopedia

An EMST of 25 random points in the plane

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane (or more generally in $\Bbb{R}^n$ ), where the weight of the edge between each pair of points is the distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines. This is much like a more difficult version of the child's game connect-the-dots.

1 Algorithms for computing EMSTs
2 Subset of Delaunay triangulation
3 Expected size
4 Applications
5 Miscellanea
6 References

[edit] Algorithms for computing EMSTs

The simplest algorithm to find an EMST, given n points, is to actually construct the complete graph on n vertices, which has n(n-1)/2 edges, compute each edge weight by finding the distance between each pair of points, and then run a standard minimum spanning tree algorithm (such as the version of Prim's algorithm or Kruskal's algorithm) on it. Since this graph has Θ(n²) edges for n distinct points, constructing it already requires Ω(n²) time. This solution also requires Ω(n²) space to store all the edges.

A better approach to finding the EMST in a plane is to note that it is a subgraph of every Delaunay triangulation of the n points, a much-reduced set of edges. Although this is not easy to see (a proof is given in the next section), if we are willing to accept it, the algorithm for finding the EMST is clear:

Compute the Delaunay triangulation, which, using a simple randomized algorithm, requires only O(n log n) expected time and O(n) expected space. Because the Delaunay triangulation is a planar graph, and there are no more than three times as many edges as vertices in any planar graph, this generates only O(n) edges.
Label each edge with its length.
Run Prim's algorithm (any variant) on it to find a minimum spanning tree. Since there are O(n) edges, this requires at most O((n+n)log n) or O(n log n) time.

The final result is an algorithm taking O(n log n) expected time and expected O(n) space.

The problem can also be generalized to n points in the d-dimensional space $\Bbb{R}^d$ . The first algorithm listed above solves this problem in O(dn²) time, if we use the d-dimensional distance function, and the second algorithm requires the same amount of time in the worst-case, since Delaunay triangulations can have Ω(n²) edges in higher dimensions. In the 1996 paper "A lower bound for randomized algebraic decision trees," Dima Grigoriev and others proved that this general problem requires at least Ω(nlog n) time for n points, but no approach to date has met this lower bound; the best solutions are close to Ω(n²) for large d.

[edit] Subset of Delaunay triangulation

The most popular efficient algorithm for computing the EMST depends on the fact that its edges are a subset of the edges in every Delaunay triangulation of the points. While this isn't clear, it's not difficult to prove.

First, there is a useful property about minimum spanning trees that we will use: if we have a cycle of points, such as v₁ → v₂ → v₃ → v₄ → v₁, it may so happen that one of the edges between adjacent points in this cycle will have a larger weight than any other. If so, this edge will not be used in any minimum spanning tree. One easy way to see this is that Kruskal's algorithm will visit this edge after all the others in the cycle; but these other edges connect all vertices in the cycle, so these vertices will all be in the same tree. Thus the new edge's two endpoints are in the same tree and it will not add this edge.

Second, we'll also be using a property of Delaunay triangulations: if there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.

Now, consider some particular fixed EMST and some particular fixed Delaunay triangulation. Suppose we take an edge e between two input points p and q which is not an edge of the Delaunay triangulation. Then, the circle C with e as its diameter must contain some other point r (or else it would prove that e is in the Delaunay triangulation). But then r is closer to both p and q than they are to each other, and so the edge from p to q is the longest edge in the cycle of points p → q → r → p. Therefore, that edge is not in the EMST.

Having shown that every edge not in the Delaunay triangulation is also not in the EMST, the contrapositive follows: that every edge in the EMST is in the Delaunay triangulation.

[edit] Expected size

The expected size of the EMST for large numbers of points has been determined by J. Michael Steele. If $f$ is the density of the probability function for picking points, then for large $n$ and $d \neq 1$ the size of the EMST is approximately

$c(d) n^{\frac{d-1}{d}} \int_{\Bbb{R}^d} f(x)^{\frac{d-1}{d}} dx$

where $c (d)$ is a constant depending only on the dimension $d$ . The exact value of the constants are unknown but can be estimated from empirical evidence.

[edit] 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. However, while these give an absolute lower bound on the amount of connection needed, most such networks prefer a k-connected graph to a tree, so that failure of an any individual link will not split the network into parts.

Another application of EMSTs 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. This realistic variation of the problem can be solved within a factor of 2 by computing the EMST, doing a walk along its boundary which outlines the entire tree, and then removing all but one occurrence of each vertex from this walk.

[edit] Miscellanea

Testing whether a tree may be drawn in the plane so that it represents the Euclidean minimum spanning tree for its vertices is NP-hard ^[1]

[edit] References

^ The realization problem for Euclidean minimum spanning trees is NP-hard (1994)

Smith College: The Open Problems Project: Problem 5: Euclidean Minimum Spanning Tree
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, and Roman Smolensky. "A lower bound for randomized algebraic decision trees." Proceedings of the 28th Annual ACM Symposium on the Theory of Computation, pages 612-619, 1996.
Max-Planck-Institut fuer Informatik: Exercise solutions, by Kavitha Telikepalli (Postscript)