Sequences of square-trees

Pilar Cano

Carleton University

Let $\mathcal{T}_S$ be the set of all non crossing spanning trees of a planar $n$-point set $S$. We prove that for each element $T$ of $\mathcal{T}_S$, there is a length-decreasing sequence of tress $T_0, \ldots, T_k$ such that $T_0=T$, $T_k=$ MST$_{\square}(S)$, $T_i$ does not cross $T_{i-1}$ for all $i=1, \ldots k$, and $k = O(\log n)$. Where MST$_{\square}(S)$ denotes the minimum spanning tree in the $L_{\infty}$ metric of the point set $S$.