Euclidean minimum spanning tree: Difference between revisions

Revision as of 07:29, 11 September 2022

Revision as of 07:36, 11 September 2022

Line 78:

===Dynamic and kinetic===

The Euclidean minimum spanning tree has been generalized in many different ways to systems of moving or changing points:

*If a set of points undergoes a sequence of dynamic insertions or deletions of points, each of these updates causesinduces 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 polylogarithmicpoly-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 that can occur, 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}}

===Lower bound===

An asymptotic lower bound of <math>\Omega(n\log n)</math> of the Euclidean minimum spanning tree problem can be established in restricted models of computation. These include the [[algebraic decision tree]] and [[algebraic computation tree]] models, in which the algorithm has access to the input points only through certain restricted primitives that perform simple algebraic computations on their coordinates. In these models, the [[closest pair of points problem]] requires <math>\Omega(n\log n)</math> time, but the closest pair is necessarily an edge of the minimum spanning tree, so the minimum spanning tree also requires this much time. Therefore, algorithms for constructing the planar minimum spanning tree in time <math>O(n\log n)</math> within this model, for instance by using the Delaunay triangulation, are optimal.{{r|yao89}} However, these lower bounds do not apply to models of computation with integer point coordinates, in which [[bitwise operation]]s and [[Random access|table indexing]] operations areon permittedthose usingcoordinates thoseare coordinatespermitted. In these models, faster algorithms are possible, as described above.{{r|bm09}}

== Applications ==

An obvious application of Euclidean minimum spanning trees is to find the cheapest network of wires or pipes to connect a set of places, assuming the links cost a fixed amount per unit length. The first publications on minimum spanning trees more generally concerned a geographic version of the problem, involving the design of an [[electrical grid]] for [[South Moravian Region|southern Moravia]],{{r|history}} and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger.{{r|lobwei}}

Minimum spanning trees are closely related to [[single-linkage clustering]], one of several methods for [[hierarchical clustering]]. The edges of a minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Once these edges have been found, by any algorithm, they may be used to construct the single-linkage clustering in time <math>O(n\log n)</math>.{{r|gowros}} Although the long thin cluster shapes produced by single-linkage clustering can be a bad fit for certain types of data, such as [[Mixture model|mixtures of Gaussian distributions]], it can be a good choice in applications where the clusters themselves are expected to have long thin shapes, such as in modeling the [[dark matter halo]]s of [[galaxy|galaxies]].{{r|mrg}} In [[geographic information science]], several researcher groups of researchers have used minimum spanning trees of the centroids of buildings to identify meaningful clusters of buildings, for instance by removing edges identified in some other way as inconsistent.{{r|urban}}

Minimum spanning trees have also been used to infer the shape of curves in the plane, given points sampled along the curve. For a smooth curve, sampled more finely than its [[local feature size]], the minimum spanning tree will form a path connecting consecutive points along the curve. SimilarMore generally, similar methods can be used more generally to recognize curves drawn in a dotted or dashed style rather than as a single connected set. Applications of this curve-finding technique include [[particle physics]], in automatically identifying the tracks left by particles in a [[bubble chamber]].{{r|zahn}} More sophisticated versions of this idea can find curves from a cloud of noisy sample points that roughly follows the curve outline, by using the topology of the spanning tree to guide a [[moving least squares]] method.{{r|lee}}

Another application of minimum spanning trees is a [[constant-factor approximation algorithm]] for the [[Euclidean traveling salesman problem]], the problem of finding the shortest [[polygonalization]] of a point set. Walking around the boundary of the minimum spanning tree can approximate the optimal traveling salesman tour within a factor of two of the optimal length.{{r|shahoe}} However, more accurate [[polynomial time approximation scheme|polynomial-time approximation scheme]]s are known for this problem.{{r|bargot}} In [[wireless ad hoc network]]s, [[Broadcasting (networking)|broadcasting]] messages along paths in a minimum spanning tree can be an accurate approximation to the minimum-energy broadcast routing, which is, again, hard to compute exactly.{{r|wclf|chrvp|fknp|ambuhl}}

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