School Seminars and Colloquia

Random Geometric Graphs Induced by Stationary Point Processes

Stochastic Processes Seminar

by Volker Schmidt


Institution: Ulm University, Institute of Stochastics
Date: Fri 2nd March 2012
Time: 4:15 PM
Location: Room 215, Richard Berry Building

Abstract: For any locally finite set M in the Euclidean space of dimension
at least 2, the minimal spanning forest MSF(M) is a generalization
of the minimal spanning tree that was introduced originally by
Aldous and Steele (1992). They conjectured that MSF(X) is almost
surely connected if X is a homogeneous Poisson point process.
This conjecture was proven in Alexander (1995) for dimension 2.
However, it remains open for higher dimensions (and for non--Poisson
point processes X).

In the present talk we introduce a family of approximations
of the minimal spanning forest, see [1]. Using techniques of
Blaszczyszyn and Yogeshwaran (2011) and Daley and Last (2005)
we prove the a.s. connectivity of the constructed approximations
for all stationary point processes X with finite range of dependence
and absolutely continuous second factorial moment measure.
We also derive conditions for the a.s. finiteness of cells in the
two-dimensional case and discuss some applications to spatial
stochastic modeling of telecommunication networks, see [2] and [3].


[1] Hirsch, C., Neuhaeuser, D. and Schmidt, V. (2012)
Connectivity of random geometric graphs related to minimal spanning forests.
Preprint (submitted).

[2] Gloaguen, C., Voss, F. and Schmidt, V. (2011)
Parametric distributions of connection lengths for the efficient analysis
of fixed access networks. Annals of Telecommunications 66, 103-118.

[3] Neuhaeuser, D., Hirsch, C., Gloaguen, C. and Schmidt, V. (2012)
On the distribution of typical shortest-path lengths in connected
random geometric graphs. Queueing Systems (in print).