The radial spanning tree of a Poisson point process

DOI10.1214/105051606000000826zbMATH Open1136.60007arXivmath/0703024OpenAlexW3105394487MaRDI QIDQ2467121FDOQ2467121

Francois Baccelli, Charles Bordenave

Publication date: 18 January 2008

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

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.

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

zbMATH Keywords

spanning treesPoisson point processasymptotic shapedirected spanning treenearest neighbor graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

• On a random directed spanning tree
• Radial generation of n-dimensional poisson processes
• Optimal paths on the space-time SINR random graph
• Large Deviations for the Graph Distance in Supercritical Continuum Percolation
• Remarks on Asymptotic Independence
• Directed, cylindric and radial Brownian webs
• Scaling limit for a family of coalescing radial random paths absorbed at the origin
• Poisson sphere counting processes with random radii
• Traffic flow densities in large transport networks
• Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks
• Semi-Infinite Paths of the Two-Dimensional Radial Spanning Tree
• Asymptotics of geometrical navigation on a random set of points in the plane
• Directed spanning forest for Ginibre ensemble is a tree
• The 2D‐directed spanning forest is almost surely a tree
• The bi-dimensional directed IDLA forest
• Quantitative two-scale stabilization on the Poisson space
• Transmission and navigation on disordered lattice networks, directed spanning forests and Brownian web
• Sublinearity of the number of semi-infinite branches for geometric random trees
• Central limit theorems for the radial spanning tree
• Navigation on a Poisson point process
• Limit theorems for random spatial drainage networks
• The directed spanning forest in the hyperbolic space
• The 2D-directed spanning forest converges to the Brownian web

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Poisson trees, succession lines and coalescing random walks 👍 👎

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)