Two trees are better than one

Abstract

We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees of the original set and of the two parts. If $w(P)$ denotes the length of a minimum spanning tree of $P$, we show that every set $P$ of $n\ge 12$ points admits a bipartition $P=R\cup B$ for which the ratio $\frac{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 very fast algorithm that computes such a bipartition in $O(1)$ time and one that computes the corresponding ratio in $O(n\log n)$ time. In certain settings, a ratio larger than $1$ can be expected and sometimes guaranteed. For example, if $P$ is a set of $n$ random points uniformly distributed in $[0,1{]}^2$ ($n\to \infty$), then for any $\eps>0$, the above ratio in a maximizing partition is at least $\sqrt2 -\eps$ with probability tending to $1$. As another example, if $P$ is a set of $n$ points with spread at most $\alpha \sqrt{n}$, for some constant $\alpha >0$, then the aforementioned ratio in a maximizing partition is $1+\Omega ({\alpha }^{-2})$. All our results and techniques are extendable to higher dimensions.

2 figures, 11 pages