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:
“After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.”
—Barbara Ehrenreich (20th century)
“A pinecone does not fall far from the tree trunk.”
—Estonian. Trans. by Ilse Lehiste (1993)