On the connectivity threshold for general uniform metric spaces
Let mu be a measure supported on a compact connected subset of an Euclidean space, which satisfies a uniform d-dimensional decay of the volume of balls of the type alpha delta(d) <= mu(B(x, delta)) <= beta delta(d) (1) where d is a fixed constant. We show that the maximal edge in the minimum spanning tree of n independent samples from mu is, with high probability approximate to(log n/n)(1/d). While previous studies on the maximal edge of the minimum spanning tree attempted to obtain the exact asymptotic, we on the other hand are interested only on the asymptotic up to multiplication by a constant. This allows us to obtain a more general and simpler proof than previous ones. (C) 2010 Elsevier B.V. All rights reserved.
connectivity threshold random networks sensor networks fractal