Euclidean minimum spanning tree: Difference between revisions

Revision as of 07:10, 11 September 2022

Revision as of 07:14, 11 September 2022

Line 21:

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 <math>n</math>-dimensional space the maximum possible [[degree (graph theory)|degree]] of a vertex (the number of spanning tree edges touchingconnected to it) equals the kissing number of spheres in <math>n</math> dimensions.{{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}} The only higher dimensions in 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 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}}