×

Rates of convergence of means for distance-minimizing subadditive Euclidean functionals. (English) Zbl 0809.60016

Author’s summary: Functionals \(L\) on finite subsets \(A\) of \(\mathbb{R}^ d\) are considered for which the value is the minimum total edge length among a class of graphs with vertex set equal to, or in some cases containing, \(A\). Examples include minimal spanning trees, the traveling salesman problem, minimal matching and Steiner trees. Beardwood, Halton and Hammersley, and later Steele, have shown essentially that for \(\{X_ 1, \dots, X_ n\}\) a uniform i.i.d. sample from \([0,1]^ d\), \(EL(\{X_ 1, \dots, X_ n\})/n^{(d - 1)/d}\) converges to a finite constant. Here we bound the rate of this convergence, proving a conjecture of Beardwood, Halton and Hammersley.

MSC:

60D05 Geometric probability and stochastic geometry
05C80 Random graphs (graph-theoretic aspects)
90C27 Combinatorial optimization
Full Text: DOI