Euclidean minimum spanning tree: Difference between revisions

Revision as of 07:59, 11 September 2022

Latest revision as of 19:53, 5 February 2025

(24 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Shortest network connecting a set of points in the plane}}

{{good article}}

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

Line 7 ⟶ 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 23 ⟶ 24:

The same 60° angle bound also occurs in the [[kissing number]] problem, of finding the maximum number of [[unit sphere]]s in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a [[star (graph theory)|star]], with the central point adjacent to all other points. Conversely, for any vertex <math>v</math> of any minimum spanning tree, one can construct non-overlapping unit spheres centered at <math>v</math> and at points two units along each of its edges, with a tangency for each neighbor of <math>v</math>. Therefore, in <math>n</math>-dimensional space the maximum possible [[degree (graph theory)|degree]] of a vertex (the number of spanning tree edges connected to it) equals the kissing number of spheres in <math>n</math> dimensions.{{r|robsal}} Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five.{{r|monsur}} Three-dimensional minimum spanning trees have degree at most twelve.{{r|robsal}} The only higher dimensions in which the exact value of the kissing number is known are four, eight, and 24 dimensions.{{r|kissing}}

For points generated at random from a given continuous distribution, the minimum spanning tree is [[almost surely]] unique. The numbers of vertices of any given degree (if that degree is possible) converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.{{r|sse}}

===Empty regions===

Line 29 ⟶ 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 44 ⟶ 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 80 ⟶ 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 96 ⟶ 97:

==Realization==

The ''realization problem'' for Euclidean minimum spanning trees takes an abstract [[tree (graph theory)|tree]] as input and seeks a geometric ___location for each vertex of the tree (in a space of some fixed dimension), such that the given tree equals the minimum spanning tree of those points with these locations. Not every abstract tree has such a realization; for instance, the tree must obey the [[kissing number]] bound on the degree of each vertex. Additional restrictions exist; for instance, it is not possible for a planar minimum spanning tree to have a degree-six vertex adjacent to a vertex of degree five or six.{{r|monsur}} Determining whether a two-dimensional realization exists is [[NP-hard]]. However, the proof of hardness depends on the fact that degree-six vertices in a tree have a very restricted set of realizations: the neighbors of such a vertex must be placed on the vertices of a [[regular hexagon]] centered at that vertex.{{r|ew94}} Indeed, for trees of maximum degree five, a planar realization always exists.{{r|monsur}} Similarly, for trees of maximum degree ten, a three-dimensional realization always exists.{{r|king}} For these realizations, some trees may require edges of exponential length and bounding boxes of exponential area relative to the length of their shortest edge.{{r|abcfks}} Trees of maximum degree four have smaller planar realizations, with polynomially bounded edge lengths and bounding boxes.{{r|frakau}}

==See also==

Line 133 ⟶ 134:

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

| volume = 12808

| yearisbn = 2021}}</ref>978-3-030-83507-1

| year = 2021| s2cid = 234599877

| year = 1998}}</ref>

<ref name=abcfks>{{citation

Line 149 ⟶ 152:

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

| volume = 47

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

| year = 1980}}</ref>

<ref name=aegh>{{citation

Line 161 ⟶ 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>

| year = 1998}}</ref>

<ref name=aesw>{{citation

Line 181 ⟶ 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 192 ⟶ 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 203 ⟶ 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

| year = 1989}}</ref>

<ref name=bargot>{{citation

Line 213 ⟶ 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}}</ref>| isbn = 978-0-7695-5135-7

| s2cid = 17514182

| citeseerx = 10.1.1.409.1291

}}</ref>

<ref name=bdek>{{citation

Line 252 ⟶ 262:

| publisher = Association for Computing Machinery

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

| year = 1997}}</ref>| s2cid = 15556637

| doi-access = free

| isbn = 0-89791-878-9

}}</ref>

<ref name=bm09>{{citation

Line 264 ⟶ 277:

| title = Delaunay triangulations in {{mvar|O}}(sort({{mvar|n}})) time and more

| volume = 58

| year = 2011}}</ref>| s2cid = 11316974

}}</ref>

<ref name=bwy>{{citation

Line 277 ⟶ 291:

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

| volume = 6

| year = 1980| s2cid = 17238717 | url = https://figshare.com/articles/journal_contribution/6608108 | doi-access = free

| year = 1980}}</ref>

}}</ref>

<ref name=cck>{{citation

Line 291 ⟶ 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 302 ⟶ 318:

| title = A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

| volume = 57

| year = 2010| s2cid = 47454142 }}</ref>

<ref name=chalev>{{citation

Line 313 ⟶ 329:

| title = On levels in arrangements of curves

| volume = 29

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

}}</ref>

<ref name=chrvp>{{citation

Line 326 ⟶ 343:

| publisher = IEEE Computer Society

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

| year = 2003}}</ref>| isbn = 0-7695-1926-1

| s2cid = 17863487

}}</ref>

<ref name=clarkson>{{citation

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

| doi = 10.1007/BF01553902

| issue = 41–4

| journal = [[Algorithmica]]

| mr = 1019387

Line 337 ⟶ 356:

| title = An algorithm for geometric minimum spanning trees requiring nearly linear expected time

| volume = 4

| year = 1989| s2cid = 22176641 }}</ref>

<ref name=comment>{{citation

Line 347 ⟶ 366:

| title = Comment: Algorithms for computing relative neighborhood graph

| volume = 16

| year = 1980| bibcode = 1980ElL....16..860T }}; reply by Urquhart, [[doi:10.1049/el:19800612|pp. 860–861]]</ref>

<ref name=devillers>{{citation

Line 359 ⟶ 378:

| url = https://hal.inria.fr/inria-00167206/file/hal.pdf

| volume = 2

| year = 1992}}</ref>| s2cid = 60203

}}</ref>

<ref name=dwyer>{{citation

Line 370 ⟶ 390:

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

| volume = 6

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

}}</ref>

<ref name=eppstein>{{citation

Line 405 ⟶ 426:

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

| volume = 13

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

}}</ref>

<ref name=fknp>{{citation

Line 419 ⟶ 441:

| title = Improved approximation results for the minimum energy broadcasting problem

| volume = 49

| year = 2007}}</ref>| s2cid = 11982404

}}</ref>

<ref name=frakau>{{citation

Line 431 ⟶ 454:

| title = Polynomial area bounds for MST embeddings of trees

| volume = 44

| year = 2011}}</ref>| s2cid = 5634139

| doi-access = free

}}</ref>

<ref name=gilpol>{{citation

Line 443 ⟶ 468:

| title = Steiner minimal trees

| volume = 16

| year = 1968| issue = 1 }}</ref>

<ref name=gowros>{{citation

Line 455 ⟶ 480:

| title = Minimum spanning trees and single linkage cluster analysis

| volume = 18

| year = 1969| issue = 1
}}</ref>

<ref name=history>{{citation

Line 467 ⟶ 493:

| title = On the history of the minimum spanning tree problem

| volume = 7

| year = 1985| s2cid = 10555375 }}</ref>

<ref name=king>{{citation

Line 490 ⟶ 516:

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

| volume = 42

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

}}</ref>

<ref name=kln>{{citation

Line 515 ⟶ 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 526 ⟶ 554:

| title = Curve reconstruction from unorganized points

| volume = 17

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

}}</ref>

<ref name=lobwei>{{citation

Line 537 ⟶ 566:

| pages = 428–437

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

| volume = 4}}</ref>| s2cid = 7320964

| doi-access = free

}}</ref>

<ref name=mares>{{citation

Line 560 ⟶ 591:

| title = Transitions in geometric minimum spanning trees

| volume = 8

| year = 1992}}</ref>| s2cid = 30101649

| doi-access = free

}}</ref>

<ref name=mrg>{{citation

Line 574 ⟶ 607:

| pages = 603–612

| title = Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010

| year = 2010}}</ref>| s2cid = 186025

}}</ref>

<ref name=msvw>{{citation

Line 591 ⟶ 625:

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

| volume = 10807

| yearisbn = 2018}}</ref>978-3-319-77403-9

| year = 2018| s2cid = 4709616

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

}}</ref>

<ref name=nzz>{{citation

Line 611 ⟶ 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 622 ⟶ 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 634 ⟶ 672:

| series = Texts and Monographs in Computer Science

| title = Computational Geometry: An Introduction

| year = 1985| s2cid = 206656565 }}</ref>

<ref name=rakwz>{{citation

Line 649 ⟶ 687:

| title = A simple, faster method for kinetic proximity problems

| volume = 48

| year = 2015}}</ref>| s2cid = 18971251

| doi-access = free

| arxiv = 1311.2032

}}</ref>

<ref name=robsal>{{citation

Line 661 ⟶ 702:

| title = Low-degree minimum spanning trees

| volume = 14

| year = 1995}}</ref>| s2cid = 16040977

| doi-access = free

}}</ref>

<ref name=rzcomb>{{citation

Line 681 ⟶ 724:

| title = Kinetic Euclidean minimum spanning tree in the plane

| volume = 16

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

}}</ref>

<ref name=shahoe>{{citation

Line 693 ⟶ 737:

| title = 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975

| title-link = Symposium on Foundations of Computer Science

| year = 1975| s2cid = 40615455 }}</ref>

<ref name=ss89>{{citation

Line 705 ⟶ 749:

| title = Worst-case growth rates of some classical problems of combinatorial optimization

| volume = 18

| year = 1989| url = https://repository.upenn.edu/cgi/viewcontent.cgi?article=1048&context=oid_papers }}</ref>

| year = 1989}}</ref>

<ref name=sse>{{citation

Line 718 ⟶ 762:

| title = On the number of leaves of a Euclidean minimal spanning tree

| volume = 24

| year = 1987| jstor = 3214207 | s2cid = 29026025 }}</ref>

<ref name=steele>{{citation

Line 748 ⟶ 792:

| pages = 450–475

| title = An extended minimum spanning tree method for characterizing local urban patterns

| volume = 32}}</ref>| s2cid = 46772272

}}</ref>

<ref name=wclf>{{citation

Line 761 ⟶ 806:

| title = Minimum-energy broadcasting in static ad hoc wireless networks

| volume = 8

| year = 2002}}</ref>| s2cid = 1297518

}}</ref>

<ref name=yao82>{{citation