Two Trees Are Better than One

.We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees (MSTs) of the original set and of the two parts. If \(w(P)\) denotes the length of an MST of \(P\), we show that every set \(P\) of \(n ≥ 12\) points admits a nontrivial bipartition \(P= R ∪ B\) for which the MST-ratio \(w(R)+w(B)/w(P)\) is strictly larger than 1 and that 1 is the largest number with this property. Furthermore, we provide a fast algorithm that computes such a bipartition in \(O(1)\) time and one that computes the corresponding MST-ratio in \(O(n log n)\) time. In certain settings, a much better MST-ratio can be guaranteed. For example, if \(P\) is a set of \(n\) random points uniformly distributed in \([0,1]^2\), then for any \(ε > 0\), the MST-ratio in a maximizing partition is at least \(√ 2 -ε\) with probability tending to 1 as \(n → ∞\). Our results and techniques are extendable to higher dimensions.Keywordsspanning treebipartitionsMSC codes05C0552C1068R10