Euclidean minimum spanning tree: Difference between revisions

Revision as of 02:51, 28 August 2022

Revision as of 02:56, 28 August 2022

Line 7:

==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]] 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}}

The Euclidean minimum spanning tree may also be formulated as a [[minimum spanning tree]] of a weighted [[complete graph]], having the given points as its vertices,

with each edge's weight set to the distance between its endpoints. A Euclidean minimum spanning tree is a [[minimum spanning tree]] of this weighted graph.{{r|shahoe}} A given set of points may have more than one Euclidean minimum spanning tree. For instance, given 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}}

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 Euclidean 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, but with the additional restriction that each point touchescan touch at most two ofline segments, so the lineresult forms a segments[[polygonal chain]]. Because of this additional restriction, the optimal traveling salesperson path may be longer than the Euclidean minimum spanning tree, but it is at most twice as long.{{r|shahoe}}

*[[Geometric spanner]]s are low-weight networks that, like the Euclidean minimum spanning tree, connect all of the points. Unlike the Euclidean 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 rather than being trees.{{r|eppstein}}

==Properties==