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:
“You try to tell me anything about the newspaper business! Sir, I have been through it from Alpha to Omaha, and I tell you that the less a man knows the bigger the noise he makes and the higher the salary he commands.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“Why is it that many contemporary male thinkers, especially men of color, repudiate the imperialist legacy of Columbus but affirm dimensions of that legacy by their refusal to repudiate patriarchy?”
—bell hooks (b. c. 1955)