Euclidean minimum spanning tree: Difference between revisions

Revision as of 01:36, 25 September 2022

Latest revision as of 19:53, 5 February 2025

(17 intermediate revisions by 9 users not shown)

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

Line 45:

For <math>n</math> points in the [[unit square]] (or any other fixed shape), the total length of the minimum spanning tree edges is <math>O(\sqrt n)</math>. Some sets of points, such as points evenly spaced in a <math>\sqrt n \times \sqrt n</math> grid, attain this bound.{{r|gilpol}} For points in a unit hypercube in <math>d</math>-dimensional space, the corresponding bound is <math>O(n^{(d-1)/d})</math>.{{r|ss89}} The same bound applies to the expected total length of the minimum spanning tree for <math>n</math> points chosen uniformly and independently from a unit square or unit hypercube.{{r|steele}} Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is <math>O(1)</math>. This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The <math>O(\sqrt n)</math> bound on total length follows by application of the [[Cauchy–Schwarz inequality]].{{r|gilpol}}

Another interpretation of these results is that the average edge length for any set of points in a unit square is <math>O(1/\sqrt n)</math>, at most proportional to the spacing of points in a regular grid; and that for ''random'' points in a unit square the average length is proportional to <math>1/\sqrt n</math>. However, in the random case, with high probability the longest edge has length approximately <math display=block>\sqrt{\frac{\log n}{\pi n}},</math> longer than the average by a non-constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a [[LaplaceGumbel distribution]].{{r|penrose}}

Any [[geometric spanner]], a subgraph of a complete geometric graph whose [[Shortest path problem|shortest paths]] approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points. Several methods for constructing spanners, such as the [[greedy geometric spanner]], achieve a constant bound for this ratio.{{r|eppstein}} It has been conjectured that the [[Steiner ratio]], the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is <math>2/\sqrt{3}\approx 1.1547</math>, the ratio for three points in an [[equilateral triangle]].{{r|gilpol}}

Line 81:

*If a set of points undergoes a sequence of dynamic insertions or deletions of points, each of these updates induces a bounded amount of change to the minimum spanning tree of the points. When the update sequence is known in advance, for points in the plane, the change after each insertion or deletion can be found in time <math>O(\log^2 n)</math> per insertion or deletion.{{r|offline}} When the updates must be handled in an [[Online algorithm|online]] manner, a slower (but still poly-logarithmic) <math>O(\log^{10} n)</math> time bound is known.{{r|chadyn}} For higher-dimensional versions of the problem the time per update is slower, but still sublinear.{{r|extrema}}

*For <math>n</math> points moving linearly with constant speed, or with more general algebraic motions, the minimum spanning tree will change by a sequence of swaps, in which one edge is removed and another replaces it at a point in time where both have equal length.{{r|kti}} For linear motions, the number of changes is at most slightly larger than <math>n^{25/9}</math>.{{r|chalev}} For more general algebraic motions, there is a near-cubic upper bound on the number of swaps, based on the theory of [[Davenport–Schinzel sequence]]s.{{r|rzcomb}}

*The ''minimum moving spanning tree problem'' again concerns points moving linearly with constant speed, over an interval of time, and seeks a single tree that minimizes the maximum sum of weights occurring at any instant during this interval. It is [[NP-hard]] to compute exactly, but can be approximated to within a factor of two in polynomial time.{{r|abb}}

*The [[kinetic Euclidean minimum spanning tree]] problem asks for a [[kinetic data structure]] that can maintain the minimum spanning tree as its points undergo both continuous motions and insertions and deletions. Several papers have studied such structures,{{r|bgz|aegh|rzkin|rakwz|msvw}} and a kinetic structure for algebraically moving points with near-cubic total time, nearly matching the bound on the number of swaps, is known.{{r|rakwz}}

Line 134:

| title = Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings

| volume = 12808

| isbn = 978-3-030-83507-1

| year = 2021| s2cid = 234599877

}}</ref>

Line 151 ⟶ 152:

| title = On the area requirements of Euclidean minimum spanning trees

| volume = 47

| year = 2014}}</ref>| doi-access = free

}}</ref>

<ref name=aegh>{{citation

Line 163 ⟶ 165:

| publisher = IEEE Computer Society

| title = 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA

| year = 1998| isbn = 0-8186-9172-7 | s2cid = 2559456 | url = https://infoscience.epfl.ch/record/99344/files/AgarwalEGH98.pdf }}</ref>

<ref name=aesw>{{citation

Line 183 ⟶ 185:

| last = Ambühl | first = Christoph

| editor1-last = Caires | editor1-first = Luís

| editor2-last = Italiano | editor2-first = Giuseppe F. | editor2-link = Giuseppe F. Italiano

| editor3-last = Monteiro | editor3-first = Luís

| editor4-last = Palamidessi | editor4-first = Catuscia | editor4-link = Catuscia Palamidessi

| editor5-last = Yung | editor5-first = Moti

| contribution = An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks

Line 194 ⟶ 196:

| title = Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings

| volume = 3580

| isbn = 978-3-540-27580-0

| year = 2005}}</ref>

Line 205 ⟶ 208:

| pages = 1220–1233

| title = Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016

| year = 2016}}</ref>| doi-access = free

| isbn = 978-1-61197-433-1

}}</ref>

<ref name=bargot>{{citation

Line 215 ⟶ 220:

| pages = 698–706

| title = 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA

| year = 2013| s2cidisbn = 17514182978-0-7695-5135-7

| s2cid = 17514182

| citeseerx = 10.1.1.409.1291

}}</ref>

Line 256 ⟶ 263:

| title = Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997

| year = 1997| s2cid = 15556637

| doi-access = free

| isbn = 0-89791-878-9

}}</ref>

Line 282 ⟶ 291:

| title = Optimal expected-time algorithms for closest point problems

| volume = 6

| year = 1980| s2cid = 17238717 | url = https://figshare.com/articles/journal_contribution/Optimal_expected-time_algorithms_for_closest-point_problems/6608108 }}</ref>| doi-access = free

}}</ref>

<ref name=cck>{{citation

Line 296 ⟶ 306:

| title = Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings

| volume = 6049

| isbn = 978-3-642-13192-9

| year = 2010}}</ref>

Line 318 ⟶ 329:

| title = On levels in arrangements of curves

| volume = 29

| year = 2003| s2cid = 18966889 | doi-access = free
}}</ref>

<ref name=chrvp>{{citation

Line 331 ⟶ 343:

| publisher = IEEE Computer Society

| title = 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings

| year = 2003| s2cidisbn = 178634870-7695-1926-1

| s2cid = 17863487

}}</ref>

Line 337 ⟶ 350:

| last = Clarkson | first = Kenneth L. | author-link = Kenneth L. Clarkson

| doi = 10.1007/BF01553902

| issue = 1-41–4

| journal = [[Algorithmica]]

| mr = 1019387

Line 377 ⟶ 390:

| title = Higher-dimensional Voronoi diagrams in linear expected time

| volume = 6

| year = 1991}}</ref>| doi-access = free

}}</ref>

<ref name=eppstein>{{citation

Line 412 ⟶ 426:

| title = Dynamic Euclidean minimum spanning trees and extrema of binary functions

| volume = 13

| year = 1995| s2cid = 7339165 | doi-access = free
}}</ref>

<ref name=fknp>{{citation

Line 440 ⟶ 455:

| volume = 44

| year = 2011| s2cid = 5634139

| doi-access = free

}}</ref>

Line 500 ⟶ 516:

| title = A randomized linear-time algorithm to find minimum spanning trees

| volume = 42

| year = 1995| s2cid = 832583 | doi-access = free
}}</ref>

<ref name=kln>{{citation

Line 525 ⟶ 542:

| title = On minimum and maximum spanning trees of linearly moving points

| volume = 13

| year = 1995}}</ref>| doi-access = free

}}</ref>

<ref name=lee>{{citation

Line 536 ⟶ 554:

| title = Curve reconstruction from unorganized points

| volume = 17

| year = 2000}}</ref>| citeseerx = 10.1.1.56.1432

}}</ref>

<ref name=lobwei>{{citation

Line 548 ⟶ 567:

| title = Formal procedures for connecting terminals with a minimum total wire length

| volume = 4| s2cid = 7320964

| doi-access = free

}}</ref>

Line 572 ⟶ 592:

| volume = 8

| year = 1992| s2cid = 30101649

| doi-access = free

}}</ref>

Line 604 ⟶ 625:

| title = LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings

| volume = 10807

| isbn = 978-3-319-77403-9

| year = 2018| s2cid = 4709616

| url = https://research.tue.nl/nl/publications/bde45eae-314a-42b4-8dca-9a0a420f38e1

Line 626 ⟶ 648:

| title = Offline algorithms for dynamic minimum spanning tree problems

| volume = 17

| year = 1994| url = https://escholarship.org/uc/item/6j46j8nc }}</ref>

<ref name=penrose>{{citation

Line 637 ⟶ 659:

| title = The longest edge of the random minimal spanning tree

| volume = 7

| year = 1997}}</ref>| doi-access = free

}}</ref>

<ref name=presha>{{citation

Line 665 ⟶ 688:

| volume = 48

| year = 2015| s2cid = 18971251

| doi-access = free

| arxiv = 1311.2032

}}</ref>

Line 678 ⟶ 703:

| volume = 14

| year = 1995| s2cid = 16040977

| doi-access = free

}}</ref>

Line 698 ⟶ 724:

| title = Kinetic Euclidean minimum spanning tree in the plane

| volume = 16

| year = 2012}}</ref>| doi-access = free

}}</ref>

<ref name=shahoe>{{citation