Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric

We study the problem of approximating MST(P), the minimum weight spanning tree of a set P of n points in d[0,1], by a spanning tree of some subset Q⊂P. We show that if the weight of MST(P) is to be approximated, then in general Q must be large. If the shape of MST(P) is to be approximated, then this is always possible with a small Q.More specifically, for any 0<ε<1 we prove:(i)There are sets P⊂d[0,1] of arbitrarily large size n with the property that any subset Q′⊂P that admits a spanning tree T′ with ||T′|−|MST(P)||<ε⋅|MST(P)| must have size at least Ω(n1−1/d). (Here |T| denotes the weight, i.e. the sum of the edge lengths of tree T.)(ii)For any P⊂d[0,1] of size n there exists a subset Q⊆P of size O(1/εd) that admits a spanning tree T that is ε-close to MST(P) in terms of Hausdorff distance (which measures shape dissimilarity).(iii)This set Q and this spanning tree T can be computed in time O(τd,p(n)+1/εdlog(1/εd)) for any fixed dimension d. Here τd,p(n) denotes the time necessary to compute the minimum weight spanning tree of n points in Rd under any fixed metric Lp, 1⩽p⩽∞, where τ2,p(n)=O(nlogn), see [D.T. Lee, Two-dimensional Voronoi diagrams in the Lp-metric, J. ACM 27 (4) (1980) 604–618], τ3,2(n)=O((nlogn)4/3), and τd,2(n)=O(n2−2/(⌈d/2⌉+1)+ϕ), with ϕ>0 arbitrarily small, for d>3, see [Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, Emo Welzl, Euclidean minimum spanning trees and bi-chromatic closest pairs, Discrete Comput. Geom. 6 (5) (1991) 407–422]. Also τ3,1(n) and τ3,∞(n) is known to be O(nlogn), see [Drago Krznaric, Christos Levcopoulos, Bengt J. Nilsson, Minimum spanning trees in d dimensions, Nordic J. of Computing 6 (4) (1999) 446–461].