Euclidean minimum spanning tree: Difference between revisions

Revision as of 02:56, 28 August 2022

Revision as of 02:58, 28 August 2022

Line 16:

==Properties==

===Angles and vertex degrees===

[[File:Kissing-3d.png|thumb|Twelve unit spheres all tangent to a central unit sphere. The Euclidean minimum spanning tree of their 13 center points has degree 12 at the central point.]]

Whenever two edges of a Euclidean minimum spanning tree meet at a vertex, they must form an angle of 60° or more, with equality only when they form two sides of an [[equilateral triangle]]. This is because, for two edges forming any sharper angle, one of the two edges could be replaced by the third, shorter edge of the triangle they form, forming a tree with smaller total length.{{r|1steiner}} In comparison, the Steiner tree problem has a stronger angle bound: an optimal Steiner tree has all angles at least 120°.{{r|gilpol}}

The same 60° angle bound also occurs in the [[kissing number]] problem, of finding the maximum number of [[unit sphere]]s in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a [[star (graph theory)|star]], with the central point adjacent to all other points. Conversely, for any vertex <math>v</math> of any minimum spanning tree, one can construct non-overlapping unit spheres centered at <math>v</math> and at points two units along each of its edges, with a tangency for each neighbor of <math>v</math>. Therefore, in space of any dimension the maximum possible [[degree (graph theory)|degree]] of a vertex (the number of spanning tree edges touching it) equals the kissing number of spheres of that dimension.{{r|robsal}} Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five.{{r|monsur}} Three-dimensional minimum spanning trees have degree at most twelve.{{r|robsal}} However, the only higher dimensions for which the exact value of the kissing number is known are four, eight, and 24 dimensions.{{r|kissing}}

For points generated at random from a given continuous distribution, the Euclidean minimum spanning tree is [[almost surely]] unique. The numbers of vertices of any given degree (if that degree is possible) converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.{{r|sse}}

===Empty regions===

Line 37:

Because the empty-region criteria for these graphs are progressively weaker, these graphs form an ordered sequence of subgraphs. That is, using "⊆" to denote the subset relationship among their edges, these graphs have the relations:

{{bi|left=1.6|Euclidean minimum spanning tree ⊆ relative neighborhood graph ⊆ Urquhart graph ⊆ Gabriel graph ⊆ Delaunay triangulation.{{r|presha|comment}}}}

Another graph guaranteed to contain the Euclidean minimum spanning tree is the [[Yao graph]], determined for points in the plane by dividing the plane around each point into six 60° wedges and connecting each point to the nearest neighbor in each wedge. The resulting graph contains the relative neighborhood graph, because two vertices with an empty lens must be the nearest neighbors to each other in their wedges. As with many of the other geometric graphs above, this definition can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.{{r|yao82|bwy}}

===Total length===

For <math>n</math> points in the [[unit square]] (or any other fixed shape), the total length of the Euclidean 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 Euclidean 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 Euclidean 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 Euclidean minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the Euclidean 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 Euclidean 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}}

===Subdivision===