2023/12/15 by Adrian Dumitrescu, János Pach, Dumitrescu, Adrian +3 · 1 citation
Computer Science · Mathematics · Environmental Science · #Computational Geometry and Mesh Generation #Point processes and geometric inequalities #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.2312.09916
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 ≥ 12 points admits a bipartition P= R ∪ B for which the 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 very fast algorithm that computes such a bipartition in O(1) time and one that computes the corresponding ratio in O(n logn) 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 → ∞), then for any \eps>0, the above ratio in a maximizing partition is at least √2 -\eps with probability tending to 1. As another example, if P is a set of n points with spread at most α√(n), for some constant α>0, then the aforementioned ratio in a maximizing partition is 1 + Ω(α-2). All our results and techniques are extendable to higher dimensions.