Sequences of spanning trees and a fixed tree theorem
O. Aichholzer, F. Aurenhammer, and F. Hurtado
be the set of all crossing-free spanning trees of a planar
. We prove that
contains, for each of its
, a length-decreasing sequence of trees
does not cross
denotes the Euclidean minimum spanning tree of
the point set
. As an implication, the number of length-improving and
planar edge moves needed to transform a tree
. Moreover, it is possible to transform any two trees in
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
Reference: O. Aichholzer, F. Aurenhammer, and F. Hurtado.
Sequences of spanning trees and a fixed tree theorem.
Computational Geometry: Theory and Applications, 21(1-2):3-20, 2002.
Special Issue. [Report MA2-IR-00-00026, Universitat Politecnica de
Catalunya, Barcelona, Spain, 2000].