Euclidean minimum spanning tree: Difference between revisions

Revision as of 16:00, 7 December 2024

Revision as of 20:23, 1 February 2025

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 inis a [[connected set]], and which has the minimum possible total length of any such system. Such a network cannot contain a [[polygon]]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}}