Summary
Asymptotic results for the Euclidean minimal spanning tree onn random vertices inR d can be obtained from consideration of a limiting infinite forest whose vertices form a Poisson process in allR d. In particular we prove a conjecture of Robert Bland: the sum of thed'th powers of the edge-lengths of the minimal spanning tree of a random sample ofn points from the uniform distribution in the unit cube ofR d tends to a constant asn→∞.
Whether the limit forest is in fact a single tree is a hard open problem, relating to continuum percolation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D.J.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab.1, 228–266 (1991)
Aldous, D.J.: A random tree model associated with random graphs. Random Structures and Algorithms1, 383–402 (1990)
Avram, F., Bertsimas, D.: The minimum spanning tree constant in geometric probability and under the independent model: a unified approach. Technical Report, M.I.T., 1990. Ann. Appl. Probab. (to appear)
Beardwood, J., Halton, H.J., Hammersley, J.M.: The shortest path through many points. Proc. Cambridge Philos. Soc.55, 299–327 (1959)
Chartrand, G., Lesniak, L.: Graphs and diagraphs. 2nd edn. Belmont, CA: Wadsworth 1986
Daley, D.J., Vere-Jones, D.: An introduction to the theory of point processes. Berlin Heidelberg New York: Springer 1988
Ethier, S.N., Kurtz, T.G.: Markov processes: characterization and convergence. New York: Wiley 1986
Grimmett, G.R.: Percolation. Berlin Heidelberg New York: Springer 1989
Hartigan, J.A.: Consistency of single linkage for high-density clusters. J. Am. Stat. Assoc.76, 388–394 (1981)
Kesten, H.: Percolation theory and first-passage percolation. Ann. Probab.15, 1231–1271 (1987)
Pemantle, R.: Choosing a spanning tree for the integer lattice uniformly. Technical Report, Cornell University, 1989. Ann. Probab.19, 1559–1574 (1991)
Ramey, D.B.: A non-parametric test of bimodality with applications to cluster analysis. PhD thesis, Yale University, 1982
Steele, J.M.: Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab.16, 1767–1787 (1988
Steele, J.M., Shepp, L.A., Eddy, W.F.: On the number of leaves of a Euclidean spanning tree. J. Appl. Probab.24, 809–826 (1987)
Timofeev, E.A.: On finding the expected length of a random minimal tree. Theory Probab. Appl.33, 361–365 (1988)
Author information
Authors and Affiliations
Additional information
Research supported by N.S.F. Grants MCS87-11426 and MCS 90-01710
Research supported in part by N.S.F. Grant DMS88-12868, A.F.O.S.R. Grant 89-0301, ARO Grant DAAL03-89-G-0092 and NSA Grant MDA-904-H-2034
Rights and permissions
About this article
Cite this article
Aldous, D., Steele, J.M. Asymptotics for Euclidean minimal spanning trees on random points. Probab. Th. Rel. Fields 92, 247–258 (1992). https://doi.org/10.1007/BF01194923
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01194923