Extremes for the minimal spanning tree on normally distributed points

被引:30
作者
Penrose, MD [1 ]
机构
[1] Univ Durham, Dept Math Sci, Durham DH1 3LE, England
关键词
geometric probability; minimal spanning tree; nearest neighbour graph; extreme values; Poisson process; Chen-Stein method;
D O I
10.1017/S000186780000851X
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
Let n points be placed independently in v-dimensional space according to the standard v-dimensional normal distribution. Let M(n) be the longest edge-length of the minimal spanning tree on these points; equivalently let M(n) 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)M(n) - b(n) converges weakly to the Gumbel (double exponential) distribution, where b(n) are explicit constants with b(n) similar to (v - 1) log log n. We also show the same result holds if M(n) is the longest edge-length for the nearest neighbour graph on the points.
引用
收藏
页码:628 / 639
页数:12
相关论文
共 11 条