Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-12T19:47:53.878Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremes for the minimal spanning tree on normally distributed points

Part of: Geometric probability and stochastic geometry Stochastic processes Graph theory

Published online by Cambridge University Press:  01 July 2016

Mathew D. Penrose
Mathew D. Penrose*
Affiliation:
Unversity of Durham
*
∗ Postal address: Department of Mathematical Sciences, University of Durham, South Road, Durham DH1 3LE. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let n points be placed independently in ν-dimensional space according to the standard ν-dimensional normal distribution. Let Mn be the longest edge-length of the minimal spanning tree on these points; equivalently let Mn be the infimum of those r such that the union of balls of radius r/2 centred at the points is connected. We show that the distribution of (2 log n)1/2Mn - bn converges weakly to the Gumbel (double exponential) distribution, where bn are explicit constants with bn ~ (ν - 1)log log n. We also show the same result holds if Mn is the longest edge-length for the nearest neighbour graph on the points.

Keywords

Geometric probabilityminimal spanning treenearest neighbour graphextreme valuesPoisson processChen-Stein method

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry 60G70: Extreme value theory; extremal processes
Secondary: 05C05: Trees 90C27: Combinatorial optimization
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 30 , Issue 3 , September 1998 , pp. 628 - 639
Copyright
Copyright © Applied Probability Trust 1998 

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.)

References

Arratia, R., Goldstein, L. and Gordon, L. (1989). Two moments suffice for Poisson approximations: the Chen–Stein method. Ann. Prob. 17, 9–25.Google Scholar
Caroni, C. and Prescott, P. (1995). On Rohlf's method for the detection of outliers in multivariate data. J. Multivariate Anal. 52, 295–307.CrossRefGoogle Scholar
Dette, H. and Henze, N. (1989). The limit distribution of the largest nearest-neighbour link in the unit d-cube. J. Appl. Prob. 26, 67–80.CrossRefGoogle Scholar
Hadi, A. S. and Simonoff, J. S. (1993). Procedures in the identification of multiple outliers in linear models. J. Amer. Statist. Assoc. 88, 1264–1272.CrossRefGoogle Scholar
Hall, P. (1988). Introduction to the Theory of Coverage Processes. Wiley, New York.Google Scholar
Matthews, P. C. and Rukhin, A. L. (1993). Asymptotic distribution of the normal sample range. Ann. Appl. Prob. 3, 454–466.Google Scholar
Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Prob. 7, 340–361.CrossRefGoogle Scholar
Rohlf, F. J. (1975). Generalization of the gap test for the detection of multivariate outliers. Biometrics. 31, 93–101.CrossRefGoogle Scholar
Silverman, B. and Brown, T. (1978). Short distances, flat triangles and Poisson limits. J. Appl. Prob. 15, 815–825.Google Scholar
Simonoff, J. S. (1991). General approaches to stepwise identification of unusual values in data analysis. In Directions in Robust Statistics and Diagnostics: Part II, ed. Stahel, W. and Weisberg, S.. Springer, New York, pp. 223–242.Google Scholar
Steele, J. M. and Tierney, L. (1986). Boundary domination and the distribution of the largest nearest-neighbour link in higher dimensions. J. Appl. Prob. 23, 524–528.CrossRefGoogle Scholar