Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T00:54:07.252Z Has data issue: false hasContentIssue false

Connectivity of Random Geometric Graphs Related to Minimal Spanning Forests

Published online by Cambridge University Press:  04 January 2016

C. Hirsch*
Affiliation:
Ulm University
D. Neuhäuser*
Affiliation:
Ulm University
V. Schmidt*
Affiliation:
Ulm University
*
∗ Postal address: Institute of Stochastics, Ulm University, 89069 Ulm, Germany.
∗ Postal address: Institute of Stochastics, Ulm University, 89069 Ulm, Germany.
∗ Postal address: Institute of Stochastics, Ulm University, 89069 Ulm, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The almost-sure connectivity of the Euclidean minimal spanning forest MSF(X) on a homogeneous Poisson point process X ⊂ ℝd is an open problem for dimension d>2. We introduce a descending family of graphs (G n )n ≥2 that can be seen as approximations to the MSF in the sense that MSF(X)=∩n=2 ∞G n (X). For n=2, one recovers the relative neighborhood graph or, in other words, the β-skeleton with β=2. We show that almost-sure connectivity of G n (X) holds for all n≥2, all dimensions d≥2, and also point processes X more general than the homogeneous Poisson point process. In particular, we show that almost-sure connectivity holds if certain continuum percolation thresholds are strictly positive or, more generally, if almost surely X does not admit generalized descending chains.

Information

Type
Stochastic Geometry and Statistical Applications
Copyright
© Applied Probability Trust