pair of points for each subset, in time . The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the minimum spanning tree. Using these ideas, a -approximation to the minimum spanning tree may be found in time, for constant . More precisely, by choosing each representative pair to approximate the closest pair in its equivalence class, and carefully varying the quality of this approximation for different pairs, the dependence on in the time bound can be given as for any fixed dimension. 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 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 per insertion or deletion. When the updates must be handled in an online manner, a slower (but still poly-logarithmic) time bound is known. For higher-dimensional versions of the problem the time per update is slower, but still sublinear. For 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. For linear motions, the number of changes is at most slightly larger than . For more general algebraic motions, there is a near-cubic upper bound on the number of swaps, based on the theory of Davenport–Schinzel sequences. 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. 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, and a kinetic structure for algebraically moving points with near-cubic total time, nearly matching the bound on