Skip to Main content Skip to Navigation
Reports

The Radial Spanning Tree of a Poisson Point Process

François Baccelli 1 Charles Bordenave 1
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : We analyze a class of random spanning trees built on a realization of an homogeneous Poisson point process of the plane. This tree has a local construction rule and a radial structure with the origin as its root We first use stochastic geometry arguments to analyze local functionals of the random tree such as the distribution of the length of the edges or the mean degree of the vertices. Far away from the origin, these local properties are shown to be close to those of the directed spanning tree introduced by Bhatt and Roy. We then use the theory of continuous state space Markov chains to analyze some non local properties of the tree such as the shape and structure of its semi-infinite paths or the shape of the set of its vertices less than $k$ generations away from the origin. This class of spanning trees has applications in many fields and in particular in communications.
Document type :
Reports
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070309
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:00:27 PM
Last modification on : Saturday, November 28, 2020 - 10:30:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:54:13 PM

Identifiers

  • HAL Id : inria-00070309, version 1

Collections

Citation

François Baccelli, Charles Bordenave. The Radial Spanning Tree of a Poisson Point Process. [Research Report] RR-5707, INRIA. 2005, pp.73. ⟨inria-00070309⟩

Share

Metrics

Record views

434

Files downloads

384