The radial spanning tree of a Poisson point process

DOI10.1214/105051606000000826MaRDI QIDQ2467121zbMATH OpenOpenAlexFDO

Authors Charles Bordenave, Francois Baccelli

Publication date 18 January 2008

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

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

zbMATH Keywords

asymptotic shapedirected spanning treenearest neighbor graphPoisson point processspanning trees

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: We analyze a class of spatial random spanning trees built on a realization of a homogeneous Poisson point process of the plane. This tree has a simple 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 a variant of the directed spanning tree introduced by Bhatt and Roy. We then use the theory of continuous state space Markov chains to analyze some nonlocal 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.

Recommendations

• Central limit theorems for the radial spanning tree
• The coalescent point process of branching trees
• Radial generation of n-dimensional poisson processes
• Poisson sphere counting processes with random radii
• Poissonian tree constructed from independent Poisson point processes
• Poisson point process limits in size-biased Galton-Watson trees
• Branching-stable point processes
• scientific article; zbMATH DE number 1859371
• Poisson trees, succession lines and coalescing random walks

Cites work

• A matching problem and subadditive Euclidean functionals
• A New Approach to the Limit Theory of Recurrent Markov Chains
• An introduction to the theory of point processes
• Concentration of measure and isoperimetric inequalities in product spaces
• Convergence rates for probabilities of moderate deviations for sums of random variables with multidimensional indices
• Geodesics and spanning trees for Euclidean first-passage percolation.
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• scientific article; zbMATH DE number 1158743 (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 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Limit theory for random sequential packing and deposition
• Markov chains and stochastic stability
• Navigation on a Poisson point process
• On a random directed spanning tree
• On the total length of the random minimal directed spanning tree
• Percolation and minimal spanning forests in infinite graphs
• Poisson trees, succession lines and coalescing random walks
• Probability theory of classical Euclidean optimization problems
• Random Geometric Graphs
• Random minimal directed spanning trees and Dickman-type distributions
• Random oriented trees: a model of drainage networks.
• The Brownian web: characterization and convergence
• The central limit theorem for Euclidean minimal spanning trees. I
• The true self-repelling motion
• Two-dimensional Poisson trees converge to the Brownian web
• Weak laws of large numbers in geometric probability

Cited in

(32)

• Sublinearity of the number of semi-infinite branches for geometric random trees
• Route lengths in invariant spatial tree networks
• Quantitative two-scale stabilization on the Poisson space
• Transmission and navigation on disordered lattice networks, directed spanning forests and Brownian web
• The 2D-directed spanning forest converges to the Brownian web
• Navigation on a Poisson point process
• Scaling limit of the radial Poissonian web
• Directed, cylindric and radial Brownian webs
• Poissonian tree constructed from independent Poisson point processes
• Poisson sphere counting processes with random radii
• Central limit theorems for the radial spanning tree
• Optimal paths on the space-time SINR random graph
• Limit theorems for random spatial drainage networks
• Asymptotics of geometrical navigation on a random set of points in the plane
• Radial generation of n-dimensional poisson processes
• Remarks on asymptotic independence
• Local/Global Phenomena in Geometrically Generated Graphs
• On a random directed spanning tree
• Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks
• The 2D-directed spanning forest is almost surely a tree
• Traffic flow densities in large transport networks
• Large deviations for the graph distance in supercritical continuum percolation
• Semi-Infinite Paths of the Two-Dimensional Radial Spanning Tree
• Scaling limit for a family of coalescing radial random paths absorbed at the origin
• The bi-dimensional directed IDLA forest
• The directed spanning forest in the hyperbolic space
• Directed spanning forest for Ginibre ensemble is a tree
• The radial spanning tree in hyperbolic space: degree and edge-length
• Quantitative CLTs on the Poisson space via Skorohod estimates and p-Poincaré inequalities
• Large and moderate deviations in Poisson navigations
• Thick trace at infinity for the hyperbolic radial spanning tree
• Absence of percolation for infinite Poissonian systems of stopped paths

This page was built for publication: The radial spanning tree of a Poisson point process

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