Sequences of spanning trees and a fixed tree theorem

摘要

Let T_S be the set of all crossing-free spanning trees of a planar n-point set S. We prove that T_S contains, for each of its members T, a length-decreasing sequence of trees T_0,…,T_k such that T_0 = T, T_k = MST(S), T_i does not cross T_(i-1) for i = 1,…,k, and k = O(log n). Here MST(S) denotes the Euclidean minimum spanning tree of the point set S. As an implication, the number of length-improving and planar edge moves needed to transform a tree T ∈ T_S into MST(S) is only O(n log n). Moreover, it is possible to transform any two trees in T_S into each other by means of a local and constant-size edge slide operation. Applications of these results to morphing of simple polygons are possible by using a crossing-free spanning tree as a skeleton description of a polygon.