Poisson-Voronoi spanning trees with applications to the optimization of communication networks

We define a family of random trees in the plane. Their nodes of level k, k = 0,..., m are the points of a homogeneous Poisson point process Pi(k), whe reas 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 nucle us x, where x is a point of Pi(k+1), then there is an are connecting x to a ll the points of Pi(k) that belong to V. This creates a family of stationar y random trees rooted in the points of Pi(m). These random trees are useful to model the spatial organization of several types of hierarchical communi cation networks. In relation to these communication networks, it is natural to associate various cost functions with such random trees. Using point pr ocess techniques, like the exchange formula between two Palm measures, and integral geometry techniques, we show how to compute these average costs as functions of the intensity parameters of the Poisson processes. The formul as derived for the average value of these cost functions can then be exploi ted for parametric optimization purposes. Several applications to classical and mobile cellular communication networks are presented.