Euclidean minimum spanning tree: Difference between revisions

Revision as of 07:14, 11 September 2022

Revision as of 07:17, 11 September 2022

Line 42:

===Total length===

For <math>n</math> points in the [[unit square]] (or any other fixed shape), the total length of the minimum spanning tree edges is <math>O(\sqrt n)</math>. Some sets of points, such as points evenly spaced in a <math>\sqrt n \times \sqrt n</math> grid, attain this bound.{{r|gilpol}} For points in a unit hypercube in <math>d</math>-dimensional space, the corresponding bound is <math>O(n^{(d-1)/d})</math>.{{r|ss89}} The same bound applies to the expected total length of the minimum spanning tree for <math>n</math> points chosen uniformly and independently from a unit square or unit hypercube.{{r|steele}} Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is <math>O(1)</math>. This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The <math>O(\sqrt n)</math> bound on total length in turn follows by application of the [[Cauchy–Schwarz inequality]].{{r|gilpol}}

Another interpretation of these results is that the average edge length for any set of points in a unit square is <math>O(1/\sqrt n)</math>, at most proportional to the spacing of points in a regular grid; and that for ''random'' points in a unit square the average length is proportional to <math>1/\sqrt n</math>. However, in the random case, with high probability the longest edge has length approximately <math display=block>\sqrt{\frac{\log n}{\pi\, n}},</math> longer than the average by a non-constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point that is far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a [[Laplace distribution]].{{r|penrose}}

Any [[geometric spanner]], a subgraph of a complete geometric graph whose [[Shortest path problem|shortest paths]] approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points. Several methods for constructing spanners, such as the [[greedy geometric spanner]], achieve a constant bound for this ratio.{{r|eppstein}} It has been conjectured that the [[Steiner ratio]], the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is <math>2/\sqrt{3}\approx 1.1547</math>, the ratio for three points in an [[equilateral triangle]].{{r|gilpol}}