A strong law for the longest edge of the minimal spanning tree
type: Item
instance of: scholarly article
title: A strong law for the longest edge of the minimal spanning tree
zbMATH Open document ID: 0944.60015
author: Mathew D. Penrose
published in: The Annals of Probability
publication date: 1999-11-09T00:00:00Z
review text: Let \(f\) be a continuous density on a connected compact support set \(\Omega\) in \(\Re^{d}\) \((d \geq 2)\) that has smooth boundary \(\partial \Omega\). Assume \(f_{0}=\) \(\min_{\Omega}f > 0\) and define \(f_{1}=\) \(\min_{\partial \Omega}f\). Let \(\underline{X}_{n}=\) \((X_1, \dots, X_n)\) be a random sample from \(f\) and define \(Y_n\) to be the smallest \(r\) such that the union of balls of diameter \(r\) centered at \(X_1, \ldots, X_n\) is connected. This \(Y_n\) also represents the maximum edge-length of a minimum spanning tree of the vertex set \(\underline{X}_n\). It is shown that, as \(n \to \infty\), \(n \theta Y_{n}^{d}/\log n \to\) \(\max\{f_{0}^{-1}, 2(1-d^{-1})f_{1}^{-1}\}\) a.s., where \(\theta\) is the volume of the unit ball. This result disproves a conjecture made by \textit{E. Tabakis} [in: From data to knowledge: theoretical and practical aspects of classification, data analysis, and knowledge organization, 222-230 (1996; Zbl 0897.62063)] that the limit is free of \(f\).
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 60G70
Mathematics Subject Classification ID: 60F15
zbMATH DE Number: 1359646
zbMATH Keywords: geometric probability
zbMATH Keywords: connectedness
zbMATH Keywords: extreme values
reviewed by: H. N. Nagaraja
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1022677261
OpenAlex ID: W2032643924
cites work: The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1]d
cites work: Q5520521
cites work: Q4693063
cites work: Cell Growth Problems
cites work: Extremes for the minimal spanning tree on normally distributed points
cites work: The longest edge of the random minimal spanning tree
cites work: A Strong Law for the Largest Nearest-Neighbour Link between Random Points
cites work: Q4887376
DOI: 10.1214/AOP/1022677261
description: scientific article; zbMATH DE number 1359646