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:
“To expect to increase prices and then to maintain them at a higher level by means of a plan which must of necessity increase production while decreasing consumption is to fly in the face of an economic law as well established as any law of nature.”
—Calvin Coolidge (1872–1933)
“Words are finite organs of the infinite mind. They cannot cover the dimensions of what is in truth. They break, chop, and impoverish it.”
—Ralph Waldo Emerson (1803–1882)