Navigation on a Poisson point process

DOI10.1214/07-AAP472MaRDI QIDQ2426610zbMATH OpenOpenAlexFDO

Authors Charles Bordenave

Publication date 23 April 2008

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0601122

zbMATH Keywords

local weak convergencePoisson point processrandom spanning treessmall-world phenomenonstochastic geometry

Mathematics Subject Classification ID

Trees (05C05) Geometric probability and stochastic geometry (60D05) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Combinatorial optimization (90C27)

Abstract: 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 $mathbb{R}^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.

Review text

Let \(N\) be a locally finite point set obtained by a Poisson point process in \(d\)-dimensional Euclidean space. A connected graph called the navigation tree is defined on \(N\) extended with origo. A greedy navigation algorithm is analyzed and asymptotic results on long paths are given. Small-world graphs illustrate the results.

Recommendations

• Asymptotics of geometrical navigation on a random set of points in the plane
• Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks
• The radial spanning tree of a Poisson point process
• Poisson trees, succession lines and coalescing random walks

Cites work

• 1994 ACM symposium on Parallel algorithms and architectures, June 27--29, 1994, Cape May, NJ, USA
• A New Approach to the Limit Theory of Recurrent Markov Chains
• Asymptotics for first-passage times on Delaunay triangulations
• Convergence rates for probabilities of moderate deviations for sums of random variables with multidimensional indices
• Convergence Rates in the Law of Large Numbers
• Efficient routeing in Poisson small-world networks
• Geodesics and spanning trees for Euclidean first-passage percolation.
• scientific article; zbMATH DE number 17688 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1460450 (Why is no real title available?)
• scientific article; zbMATH DE number 747046 (Why is no real title available?)
• Limit theory for random sequential packing and deposition
• Location-aided routing (LAR) in mobile ad hoc networks
• Markov chains and stochastic stability
• Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks
• Navigation in small-world networks: a scale-free continuum model
• Navigation on a Poisson point process
• On the connectivity and diameter of small-world networks
• Poisson trees, succession lines and coalescing random walks
• Random minimal directed spanning trees and Dickman-type distributions
• Random oriented trees: a model of drainage networks.
• The central limit theorem for Euclidean minimal spanning trees. I
• The radial spanning tree of a Poisson point process
• The small-world phenomenon: an algorithmic perspective
• Weak laws of large numbers in geometric probability

Cited in

(12)

• Navigation in spatial networks: a survey
• Transmission and navigation on disordered lattice networks, directed spanning forests and Brownian web
• Navigation on a Poisson point process
• Connected allocation to Poisson points in \(\mathbb R^{2}\)
• The radial spanning tree of a Poisson point process
• Distribution of the smallest visited point in a greedy walk on the line
• Poissonian tree constructed from independent Poisson point processes
• Central limit theorems for the radial spanning tree
• Optimal paths on the space-time SINR random graph
• Asymptotics of geometrical navigation on a random set of points in the plane
• Traffic flow densities in large transport networks
• Large and moderate deviations in Poisson navigations

This page was built for publication: Navigation on a Poisson point process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2426610)