Algorithms For Computing EMSTs in Two Dimensions
The simplest algorithm to find an EMST in two dimensions, 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 Θ(n2) edges for n distinct points, constructing it already requires Ω(n2) time. This solution also requires Ω(n2) 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:
- 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 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 such as Borůvka's algorithm, Prim's algorithm, or Kruskal's algorithm.
The final result is an algorithm taking O(n log n) time and O(n) space.
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).
Read more about this topic: Euclidean Minimum Spanning Tree
Famous quotes containing the word dimensions:
“Is it true or false that Belfast is north of London? That the galaxy is the shape of a fried egg? That Beethoven was a drunkard? That Wellington won the battle of Waterloo? There are various degrees and dimensions of success in making statements: the statements fit the facts always more or less loosely, in different ways on different occasions for different intents and purposes.”
—J.L. (John Langshaw)