A quadratic distance bound on sliding between crossing-free spanning trees

AbstractLet S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that it is possible to transform any two trees in TS into each other by O(n2) local and constant-size edge slide operations. Previously no polynomial upper bound for this task was known, but in [O. Aichholzer, F. Aurenhammer, F. Hurtado, Sequences of spanning trees and a fixed tree theorem, Comput. Geom.: Theory Appl. 21 (1–2) (2002) 3–20] a bound of O(n2logn) operations was conjectured