Content deleted Content added
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | #UCB_CommandLine |
→Dynamic and kinetic: wlnk |
||
| (2 intermediate revisions by 2 users not shown) | |||
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}}
| |||