Rates of convergence of means of Euclidean functionals

Abstract

Let $L$ be the Euclidean functional with $p$-th power-weighted edges. Examples include the sum of the $p$-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (1994, 1996) have shown that for $n$ i.i.d. sample points $\{X_1,...,X_n\}$ from $[0,1{]}^d$, $L(\{X_1,...,X_n\})/n^{(d-p)/d}$ converges a.s. to a finite constant. Here we bound the rate of convergence of $EL(\{X_1,...,X_n\})/n^{(d-p)/d}$.

23 pages