Euclidean minimum spanning tree: Difference between revisions

Revision as of 12:59, 12 August 2023

Latest revision as of 19:53, 5 February 2025

(9 intermediate revisions by 6 users not shown)

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 164 ⟶ 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 195 ⟶ 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 207 ⟶ 209:

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

| year = 2016| doi-access = free

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

}}</ref>

Line 217 ⟶ 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 259 ⟶ 264:

| year = 1997| s2cid = 15556637

| doi-access = free

| isbn = 0-89791-878-9

}}</ref>

Line 285 ⟶ 291:

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

| volume = 6

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

}}</ref>

<ref name=cck>{{citation

Line 299 ⟶ 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 335 ⟶ 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 545 ⟶ 554:

| title = Curve reconstruction from unorganized points

| volume = 17

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

}}</ref>

<ref name=lobwei>{{citation

Line 615 ⟶ 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 678 ⟶ 689:

| year = 2015| s2cid = 18971251

| doi-access = free

| arxiv = 1311.2032

}}</ref>