On a locally finite point set, a navigation defines a path through the point set from one point to another. The set of paths leading to a given point defines a tree known as the navigation tree. In this article, we analyze the properties of the navigation tree when the point set is a Poisson point process on ℝd. We examine the local weak convergence of the navigation tree, the asymptotic average of a functional along a path, the shape of the navigation tree and its topological ends. We illustrate our work in the small-world graphs where new results are established.
Publié le : 2008-04-15
Classification:
Random spanning trees,
Poisson point process,
local weak convergence,
small-world phenomenon,
stochastic geometry,
60D05,
05C05,
90C27,
60G55
@article{1206018202,
author = {Bordenave, Charles},
title = {Navigation on a Poisson point process},
journal = {Ann. Appl. Probab.},
volume = {18},
number = {1},
year = {2008},
pages = { 708-746},
language = {en},
url = {http://dml.mathdoc.fr/item/1206018202}
}
Bordenave, Charles. Navigation on a Poisson point process. Ann. Appl. Probab., Tome 18 (2008) no. 1, pp. 708-746. http://gdmltest.u-ga.fr/item/1206018202/