Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/25870
Title: | Largest nearest-neighbour link and connectivity threshold in a polytopal random sample |
Authors: | Penrose, MD Yang, X Higgs, F |
Keywords: | stochastic geometry;random geometric graph;connectivity;isolated points |
Issue Date: | 16-Dec-2023 |
Publisher: | Springer Nature |
Citation: | Penrose, M.D., Yang, X. and Higgs, F. (2023) 'Largest nearest-neighbour link and connectivity threshold in a polytopal random sample', Journal of Applied and Computational Topology, 0 (ahead of print), pp. 1 - 28. doi: 10.1007/s41468-023-00154-5. |
Abstract: | Let X1, X2, . . . be independent identically distributed random points in a convex polytopal domain A ⊂ Rd . Define the largest nearest-neighbour link Ln to be the smallest r such that every point of Xn := {X1, . . . , Xn} has another such point within distance r .We obtain a strong law of large numbers for Ln in the large-n limit. A related threshold, the connectivity threshold Mn, is the smallest r such that the random geometric graph G(Xn, r ) is connected (so Ln ≤ Mn). We show that as n→∞, almost surely nLdn / log n tends to a limit that depends on the geometry of A, and nMd n / log n tends to the same limit. We derive these results via asymptotic lower bounds for Ln and upper bounds for Mn that are applicable in a larger class of metric spaces satisfying certain regularity conditions. |
Description: | A preprint version of the article is available at arXiv:2301.02506v1 [math.PR], https://arxiv.org/abs/2301.02506.. It has not been certified by peer-review. A CC BY or equivalent licence is applied to the AAM arising from this submission, in accordance with the grant’s open access conditions. Contributions: FH was not an author of the first version of this paper. He contributed to an improvement in the statement and proof of Lemma 3.12 of this version, and provided the simulations described in this version. Data availability: The code used to generate Fig. 2, as well as the seeds used for the samples shown, is available at https://github.com/frankiehiggs/connectivity-in-polytopes. MSC classes: 60D05, 60F15, 05C80. |
URI: | https://bura.brunel.ac.uk/handle/2438/25870 |
DOI: | https://doi.org/10.1007/s41468-023-00154-5 |
ISSN: | 2367-1726 |
Other Identifiers: | ORCiD: Xiaochuan Yang https://orcid.org/0000-0003-2435-4615 arXiv:2301.02506 [math.PR] 60D05 60F15 05C80 |
Appears in Collections: | Dept of Mathematics Research Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
FullText.pdf | Copyright © 2023 The Authors. Rights and permissions: This article is published under an open access license (https://creativecommons.org/licenses/by/4.0/). Please check the 'Copyright Information' section either on this page or in the PDF for details of this license and what re-use is permitted. If your intended use exceeds what is permitted by the license or if you are unable to locate the licence and re-use information, please contact the Rights and Permissions team. | 570.68 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License