Skip to main content
eScholarship
Open Access Publications from the University of California

Asymptotics for Euclidean minimal spanning trees on random points

  • Author(s): Aldous, D
  • Steele, JM
  • et al.
Abstract

Asymptotic results for the Euclidean minimal spanning tree on n random vertices in Rd can be obtained from consideration of a limiting infinite forest whose vertices form a Poisson process in all Rd. In particular we prove a conjecture of Robert Bland: the sum of the d'th powers of the edge-lengths of the minimal spanning tree of a random sample of n points from the uniform distribution in the unit cube of Rd tends to a constant as n→∞. Whether the limit forest is in fact a single tree is a hard open problem, relating to continuum percolation. © 1992 Springer-Verlag.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View