The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane (or more generally in ℝd), 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.
In the plane, an EMST for a given set of points may be found in Θ(n log n) time using O(n) space in the algebraic decision tree model of computation. Faster randomized algorithms of complexity O(n log log n) are known in more powerful models of computation that more accurately model the abilities of real computers.
In higher dimensions (d ≥ 3), finding an optimal algorithm remains an open problem.
Read more about Euclidean Minimum Spanning Tree: Lower Bound, Algorithms For Computing EMSTs in Two Dimensions, Higher Dimensions, Subtree of Delaunay Triangulation, Expected Size, Applications, Planar Realization
Famous quotes containing the words minimum and/or tree:
“There are ... two minimum conditions necessary and sufficient for the existence of a legal system. On the one hand those rules of behavior which are valid according to the system’s ultimate criteria of validity must be generally obeyed, and on the other hand, its rules of recognition specifying the criteria of legal validity and its rules of change and adjudication must be effectively accepted as common public standards of official behavior by its officials.”
—H.L.A. (Herbert Lionel Adolphus)
“But when the bowels of the earth were sought,
And men her golden entrails did espy,
This mischief then into the world was brought,
This framed the mint which coined our misery.
...
And thus began th’exordium of our woes,
The fatal dumb-show of our misery;
Here sprang the tree on which our mischief grows,
The dreary subject of world’s tragedy.”
—Michael Drayton (1563–1631)