HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks

Abstract : We define a family of random trees in the plane. Their nodes of level $k, k=0\thru m$ are the points of a homogeneous Poisson point process $\Pi_k$, whereas their arcs connect nodes of level $k$ and $k+1$, according to the least distance principle: if $V$ denotes the Voronoi cell w.r.t. $\Pi_k+1$ with nucleus $x$, where $x$ is a point of $\Pi_k+1$, then there is an arc connecting $x$ to all the points of $\Pi_k$ which belong to $V$. This creates a family of stationary random trees rooted in the points of $\Pi_m$. These random trees are useful to model the spatial organization of several types of hierarchical communication networks. In relation with these communication networks, it is natural to associate various cost functions with such random trees. Using point process techniques, like the exchange formula between two Palm measures, and integral geometry techniques, we show how to compute the average cost in function of the intensity parameters of the Poisson processes. The formulas which are derived for the average value of the cost function are then exploited for parametric optimization purposes.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:25:10 PM
Last modification on : Friday, February 4, 2022 - 3:15:39 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:53:43 PM


  • HAL Id : inria-00073653, version 1



François Baccelli, Sergei Zuyev. Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks. RR-3040, INRIA. 1996. ⟨inria-00073653⟩



Record views


Files downloads