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 higher processes are all processes of simplification. The novelist must learn to write, and then he must unlearn it; just as the modern painter learns to draw, and then learns when utterly to disregard his accomplishment, when to subordinate it to a higher and truer effect.”
—Willa Cather (1873–1947)
“It seems to me that we do not know nearly enough about ourselves; that we do not often enough wonder if our lives, or some events and times in our lives, may not be analogues or metaphors or echoes of evolvements and happenings going on in other people?—or animals?—even forests or oceans or rocks?—in this world of ours or, even, in worlds or dimensions elsewhere.”
—Doris Lessing (b. 1919)