Higher Dimensions
The problem can also be generalized to n points in the d-dimensional space ℝd. In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the convex hull into d-dimensional simplices) contains the minimum spanning tree; however, the triangulation might contain the complete graph. Therefore, finding the Euclidean minimum spanning tree as a spanning tree of the complete graph or as a spanning tree of the Delaunay triangulation both take O(dn2) time. For three dimensions it is possible to find the minimum spanning tree in time O((n log n)4/3), and in any dimension greater than three it is possible to solve it in a time that is faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms. For uniformly random point sets it is possible to compute minimum spanning trees as quickly as sorting.
Read more about this topic: Euclidean Minimum Spanning Tree
Famous quotes containing the words higher and/or dimensions:
“This might be the end of the world. If Joe lost we were back in slavery and beyond help. It would all be true, the accusations that we were lower types of human beings. Only a little higher than apes. True that we were stupid and ugly and lazy and dirty and, unlucky and worst of all, that God Himself hated us and ordained us to be hewers of wood and drawers of water, forever and ever, world without end.”
—Maya Angelou (b. 1928)
“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)