Euclidean minimum spanning tree: Difference between revisions

Revision as of 07:27, 29 January 2023

Revision as of 10:53, 31 March 2023

Line 1:

{{good article}}

{{Short description|Shortest network connecting points}}

{{good article}}

[[Image:Euclidean minimum spanning tree.svg|thumb|300px|right|Euclidean minimum spanning tree of 25 random points in the plane]]

Line 8:

==Definition and related problems==

A Euclidean minimum spanning tree, for a set of <math>n</math> points in the [[Euclidean plane]] or [[Euclidean space]], is a system of [[line segment]]s, having only the given points as their endpoints, whose union includes all of the points in a [[connected set]], and which has the minimum possible total length of any such system. Such a network cannot contain a [[polygon|polygonal]]al ring of segments; if one existed, the network could be shortened by removing an edge of the polygon. Therefore, the minimum-length network forms a [[Tree (graph theory)|tree]]. This observation leads to the equivalent definition that a Euclidean minimum spanning tree is a tree of line segments between pairs of the given points, of minimum total length.{{r|gowros}} The same tree may also be described as a [[minimum spanning tree]] of a weighted [[complete graph]], having the given points as its vertices and the distances between points as edge weights.{{r|shahoe}} The same points may have more than one minimum spanning tree. For instance, for the vertices of a [[regular polygon]], removing any edge of the polygon produces a minimum spanning tree.{{r|bdek}}

Publications on the Euclidean minimum spanning tree commonly abbreviate it as "EMST".{{r|aesw|mrg}} They may also be called "geometric minimum spanning trees",{{r|clarkson|monsur}} but that term may be used more generally for geometric spaces with non-Euclidean distances, such as [[Lp space|{{math|''L''^''p''}} spaces]].{{r|nzz}} When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".{{r|frakau|king|kln}}

Line 30:

For any edge <math>uv</math> of any Euclidean minimum spanning tree, the [[Lens (geometry)|lens]] (or [[vesica piscis]]) formed by intersecting the two circles with <math>uv</math> as their radii cannot have any other given vertex <math>w</math> in its interior. Put another way, if any tree has an edge <math>uv</math> whose lens contains a third point <math>w</math>, then it is not of minimum length. For, by the geometry of the two circles, <math>w</math> would be closer to both <math>u</math> and <math>v</math> than they are to each other. If edge <math>uv</math> were removed from the tree, <math>w</math> would remain connected to one of <math>u</math> and <math>v</math>, but not the other. Replacing the removed edge <math>uv</math> by <math>uw</math> or <math>vw</math> (whichever of these two edges reconnects <math>w</math> to the vertex from which it was disconnected) would produce a shorter tree.{{r|gilpol}}

For any edge <math>uv</math> of any Euclidean minimum spanning tree, the [[rhombus]] with angles of 60° and 120°, having <math>uv</math> as its long diagonal, is disjoint from the rhombi formed analogously by all other edges. Two edges sharing an endpoint cannot have overlapping rhombi, because that would imply aan edge angle sharper than 60°, and two disjoint edges cannot have overlapping rhombi; if they did, the longer of the two edges could be replaced by a shorter edge among the same four vertices.{{r|gilpol}}

===Supergraphs===