Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability
John M. Steele · The Annals of Probability · 1981
A limit theorem is established for a class of random processes (called here subadditive Euclidean functionals) which arise in problems of geometric probability. Particular examples include the length of shortest path through a random sample, the length of a rectilinear Steiner tree spanned by a sample, and the length of a minimal matching. Also, a uniform convergence theorem is proved which is needed in Karp's probabilistic algorithm for the traveling salesman problem.