Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-18T15:07:22.380Z Has data issue: false hasContentIssue false

On the number of leaves of a euclidean minimal spanning tree

Published online by Cambridge University Press:  14 July 2016

J. Michael Steele*
Affiliation:
Princeton University
Lawrence A. Shepp*
Affiliation:
AT&T Bell Laboratories
William F. Eddy*
Affiliation:
Carnegie-Mellon University
*
∗ Postal address: Program in Engineering Statistics, Princeton University, Princeton, NJ 08544, USA.
∗∗ Postal address: AT&T Bell Laboratories, Murray Hill, NJ 07974, USA.
∗∗∗ Postal address: Department of Statistics, Carnegie-Mellon University, Pittsburgh, PA 15213, USA.

Abstract

Let Vk,n be the number of vertices of degree k in the Euclidean minimal spanning tree of Xi , , where the Xi are independent, absolutely continuous random variables with values in Rd. It is proved that n –1 Vk,n converges with probability 1 to a constant α k,d. Intermediate results provide information about how the vertex degrees of a minimal spanning tree change as points are added or deleted, about the decomposition of minimal spanning trees into probabilistically similar trees, and about the mean and variance of Vk,n.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1987 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable