Editing Euclidean minimum spanning tree (section)

==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]]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''<sup>''p''</sup>}} spaces]].{{r|nzz}} When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".{{r|frakau|king|kln}}

Several other standard geometric networks are closely related to the Euclidean minimum spanning tree:
*The [[Steiner tree problem]] again seeks a system of line segments connecting all given points, but without requiring the segments to start and end only at given points. In this problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the minimum spanning tree.{{r|gilpol}}
*In the Euclidean [[Travelling salesman problem|traveling salesperson path problem]], the connecting line segments must start and end at the given points, like the spanning tree and unlike the Steiner tree; additionally, each point can touch at most two line segments, so the result forms a [[polygonal chain]]. Because of this restriction, the optimal path may be longer than the Euclidean minimum spanning tree, but is at most twice as long.{{r|shahoe}}
*[[Geometric spanner]]s are low-weight networks that, like the minimum spanning tree, connect all of the points. Unlike the minimum spanning tree, all of these connecting paths are required to be short, having length proportional to the distance between the points they connect. To achieve this property, these networks generally have cycles and so are not trees.{{r|eppstein}}