First Passage Percolation on Random Geometric Graphs and an Application to Shortest-Path Trees. (June 2015)

• Record Type: Journal Article
• Authors: Hirsch, C.; Neuhäuser, D.; Gloaguen, C.; Schmidt, V.
• Is Part Of: Advances in applied probability. Volume 47:Number 2(2015)
• Page Start: 328
• Page End: 354
• Publication Date: 2015-06
• Subjects: First passage percolation, -- shape theorem, -- shortest-path tree, -- longest shortest path, -- random geometric graph; 60D05, -- 05C80, -- 05C10, -- 82B43; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1239/aap/1435236978
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract : We consider Euclidean first passage percolation on a large family of connected random geometric graphs in the d -dimensional Euclidean space encompassing various well-known models from stochastic geometry. In particular, we establish a strong linear growth property for shortest-path lengths on random geometric graphs which are generated by point processes. We consider the event that the growth of shortest-path lengths between two (end) points of the path does not admit a linear upper bound. Our linear growth property implies that the probability of this event tends to zero sub-exponentially fast if the direct (Euclidean) distance between the endpoints tends to infinity. Besides, for a wide class of stationary and isotropic random geometric graphs, our linear growth property implies a shape theorem for the Euclidean first passage model defined by such random geometric graphs. Finally, this shape theorem can be used to investigate a problem which is considered in structural analysis of fixed-access telecommunication networks, where we determine the limiting distribution of the length of the longest branch in the shortest-path tree extracted from a typical segment system if the intensity of network stations converges to 0.