Euclidean minimum spanning tree

Euclidean minimum spanning tree

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".

In the plane, an EMST for a given set of points may be found in asymptotically optimal Θ("n" log "n") time using O("n") space. Randomized algorithms of complexity O{"n" log log "n"} are known.

In higher dimensions ("d" ≥ 3), finding an optimal algorithm remains an open problem.

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"2) edges for "n" distinct points, constructing it already requires Ω("n"2) time. This solution also requires Ω("n"2) 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 in O("n" log "n") time and O("n") 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") time and 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"2) 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"2) 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 has a lower bound of Ω("n"log "n") time for "n" points, but the best solutions so far are close to Ω("n"2) for large "d".

Subtree of Delaunay triangulation

A simple proof that all edges of an EMST are edges of a Delaunay triangulation of the points [Robert Pless. Lecture 17: Voronoi Diagrams and Delauney Triangulations. Spring 2003, Computational Geometry Class Page. Associate Professor of Computer Science and Engineering at Washington University. http://www.cs.wustl.edu/~pless/506/l17.html] [Robert Sedgewick and Kevin Wayne. Minimum Spanning Tree lecture notes. Computer Science 226: Algorithms & Data Structures, Spring 2007. Princeton University. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf] is in fact the proof of the equivalent contrapositive statement: "every edge not in a Delaunay triangulation is also not in any EMST." It is based on two lemmas.

Lemma 1 (the cycle property of minimum spanning trees): "For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of other edges of C, then this edge cannot belong to a MST".

Lemma 2 (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."

Consider an edge "e" between two input points "p" and "q" which is not an edge of a Delaunay triangulation. Lemma 2 implies that the circle "C" with "e" as its diameter must contain some other point "r" inside. 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", and by Lemma 1 "e" is not in any EMST.

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 eq 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.

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.

Miscellanea

Testing whether a tree may be drawn in the plane so that it represents the Euclidean minimum spanning tree for its verticesis NP-hard

This is called the realization problem for Euclidean minimum spanning trees: Given a tree T = (V, E), find a location D(u) for each vertex u in V so that T is a minimum spanning tree of {D(u) : u in V}, or determine that no such locations exist. [ [http://portal.acm.org/citation.cfm?doid=177424.177507 The realization problem for Euclidean minimum spanning trees is NP-hard (1994)] ]

References

* [http://cs.smith.edu/~orourke/TOPP/P5.html#gkms-lbrad-96 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.
* [http://www.mpi-sb.mpg.de/~kavitha/assignment10-sol.ps Max-Planck-Institut fuer Informatik: Exercise solutions] , by Kavitha Telikepalli (Postscript)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia

  • Steiner tree — The Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization.The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a… …   Wikipedia

  • Steiner tree problem — Steiner tree for three points A, B, and C (note there are no direct connections between A, B, C). The Steiner point S is located at the Fermat point of the triangle ABC …   Wikipedia

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Delaunay triangulation — A Delaunay triangulation in the plane with circumcircles shown In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of… …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • List of books in computational geometry — This is a list of books in computational geometry. There are two major, largely nonoverlapping categories: *Combinatorial computational geometry, which deals with collections of discrete objects or defined in discrete terms: points, lines,… …   Wikipedia

  • Proximity problems — is a class of problems in computational geometry which involve estimation of distances between geometric objects. A subset of these problems stated in terms of points only are sometimes referred to as closest point problems[1], although the term… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”