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:
“The white man regards the universe as a gigantic machine hurtling through time and space to its final destruction: individuals in it are but tiny organisms with private lives that lead to private deaths: personal power, success and fame are the absolute measures of values, the things to live for. This outlook on life divides the universe into a host of individual little entities which cannot help being in constant conflict thereby hastening the approach of the hour of their final destruction.”
—Policy statement, 1944, of the Youth League of the African National Congress. pt. 2, ch. 4, Fatima Meer, Higher than Hope (1988)
“I was surprised by Joe’s asking me how far it was to the Moosehorn. He was pretty well acquainted with this stream, but he had noticed that I was curious about distances, and had several maps. He and Indians generally, with whom I have talked, are not able to describe dimensions or distances in our measures with any accuracy. He could tell, perhaps, at what time we should arrive, but not how far it was.”
—Henry David Thoreau (1817–1862)