Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-24T18:41:52.443Z Has data issue: false hasContentIssue false
  • English
  • Français

Semi-Infinite Paths of the Two-Dimensional Radial Spanning Tree

Part of: Geometric probability and stochastic geometry

Published online by Cambridge University Press:  04 January 2016

François Baccelli ,
David Coupier  and
Viet Chi Tran
François Baccelli*
Affiliation:
INRIA
David Coupier*
Affiliation:
Université Lille1
Viet Chi Tran*
Affiliation:
Université Lille1
*
∗ Postal address: Research group on Network Theory and Communications (TREC), INRIA-ENS, 75214 Paris, France.
∗∗ Postal address: Laboratoire Paul Painlevé, Université Lille 1, Cité Scientifique, 59655 Villeneuve d'Ascq Cedex, France.
∗∗ Postal address: Laboratoire Paul Painlevé, Université Lille 1, Cité Scientifique, 59655 Villeneuve d'Ascq Cedex, France.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study semi-infinite paths of the radial spanning tree (RST) of a Poisson point process in the plane. We first show that the expectation of the number of intersection points between semi-infinite paths and the sphere with radius r grows sublinearly with r. Then we prove that in each (deterministic) direction there exists, with probability 1, a unique semi-infinite path, framed by an infinite number of other semi-infinite paths of close asymptotic directions. The set of (random) directions in which there is more than one semi-infinite path is dense in [0, 2π). It corresponds to possible asymptotic directions of competition interfaces. We show that the RST can be decomposed into at most five infinite subtrees directly connected to the root. The interfaces separating these subtrees are studied and simulations are provided.

Keywords

Stochastic geometryrandom treesemi-infinite pathasymptotic directioncompetition interface

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 45 , Issue 4 , December 2013 , pp. 895 - 916
Copyright
© Applied Probability Trust 

References

Athreya, S., Roy, R. and Sarkar, A. (2008). Random directed trees and forest-drainage networks with dependence. Electron. J. Prob. 13, 2160–2189.Google Scholar
Baccelli, F. and Bordenave, C. (2007). The radial spanning tree of a Poisson point process. Ann. Appl. Prob. 17, 305–359.Google Scholar
Bonichon, N and Marckert, J.-F. (2011). Asymptotics of geometrical navigation on a random set of points in the plane. Adv. Appl. Prob. 43, 889–942.Google Scholar
Coupier, D. (2011). Multiple geodesics with the same direction. Electron. Commun. Prob. 16, 517–527.Google Scholar
Coupier, D. and Heinrich, P. (2011). Stochastic domination for the last passage percolation tree. Markov Process. Relat. Fields 17, 37–48.Google Scholar
Coupier, D. and Heinrich, P. (2012). Coexistence probability in the last passage percolation model is 6-8 log 2. Ann. Inst. H. Poincaré Prob. Statist. 48, 973–988.Google Scholar
Coupier, D. and Tran, V. C. (2013). The 2D-directed spanning forest is almost surely a tree. Random Structures Algorithms 42, 59–72.Google Scholar
Ferrari, P. A. and Pimentel, L. P. R. (2005). Competition interfaces and second class particles. Ann. Prob. 33, 1235–1254.Google Scholar
Gangopadhyay, S., Roy, R. and Sarkar, A. (2004). Random oriented trees: a model of drainage networks. Ann. App. Prob. 14, 1242–1266.Google Scholar
Howard, C. D. and Newman, C. M. (1997). Euclidean models of first-passage percolation. Prob. Theory Relat. Fields 108, 153–170.CrossRefGoogle Scholar
Howard, C. D. and Newman, C. M. (2001). Geodesics and spanning trees for Euclidean first-passage percolation. Ann. Prob. 29, 577–623.Google Scholar
Jacod, J. and Shiryaev, A. N. (1987). Limit Theorems for Stochastic Processes. Springer, Berlin.CrossRefGoogle Scholar
Norris, J. and Turner, A. G. (2012). Hastings-Levitov aggregation in the small-particle limit. Commun. Math. Phys. 316, 809–841.Google Scholar
Pimentel, L. P. R. (2007). Multitype shape theorems for first passage percolation models. Adv. Appl. Prob. 39, 53–76.Google Scholar
Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81, 73–205.Google Scholar