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 Ti-1 for i = l,...,k, and k = O(logn). 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 is an element of 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. (C) 2002 Elsevier Science B.V. All rights reserved.