Extremes for the Minimal Spanning Tree on Normally Distributed Points

By Mathew D. Penrose.

Let n points be placed independently in d-dimensional space according to the standard d-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/2 Mn - bn converges weakly to the Gumbel (double exponential) distribution, where bn are explicit constants which are asymptotic to (d-1) log log n as n becomes large. We also show the same result holds if Mn is the longest edge-length for the nearest neighbour graph on the points.

Advances in Applied Probability 30, 628-639 (1998).