Advances in Applied Probability

First passage percolation on random geometric graphs and an application to shortest-path trees

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.

Article information

Source
Adv. in Appl. Probab., Volume 47, Number 2 (2015), 328-354.

Dates
First available in Project Euclid: 25 June 2015

Permanent link to this document
https://projecteuclid.org/euclid.aap/1435236978

Digital Object Identifier
doi:10.1239/aap/1435236978

Mathematical Reviews number (MathSciNet)
MR3360380

Zentralblatt MATH identifier
1355.60018

Citation

Hirsch, C.; Neuhäuser, D.; Gloaguen, C.; Schmidt, V. First passage percolation on random geometric graphs and an application to shortest-path trees. Adv. in Appl. Probab. 47 (2015), no. 2, 328--354. doi:10.1239/aap/1435236978. https://projecteuclid.org/euclid.aap/1435236978
{"ft_lang_label":"__label__en","ft_lang_prob":0.7603577,"math_prob":0.7492262,"size":2528,"snap":"2019-43-2019-47","text_gpt3_token_len":615,"char_repetition_ratio":0.124801904,"word_repetition_ratio":0.057803467,"special_character_ratio":0.24643987,"punctuation_ratio":0.15929204,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9747027,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-20T23:42:48Z\",\"WARC-Record-ID\":\"<urn:uuid:f2ac822a-9d5e-40e6-ad0c-70b93ec0d97e>\",\"Content-Length\":\"48111\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ca759d9d-87b6-4a58-b9c6-25a182e8af0e>\",\"WARC-Concurrent-To\":\"<urn:uuid:c5abff03-5ae8-4feb-b171-33e6234edc52>\",\"WARC-IP-Address\":\"132.236.27.47\",\"WARC-Target-URI\":\"https://projecteuclid.org/euclid.aap/1435236978\",\"WARC-Payload-Digest\":\"sha1:YETQDIAGE4HU6XETJC7WWEHAFPB5MBDB\",\"WARC-Block-Digest\":\"sha1:XHZMBPMQDZGZKYVZSMNCX6EF44TBF5LH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987750110.78_warc_CC-MAIN-20191020233245-20191021020745-00199.warc.gz\"}"}