Reconstructing Almost All of a Point Set in \(\boldsymbol{\mathbb{R}}\) d from Randomly Revealed Pairwise Distances
SIAM Journal on Discrete Mathematics · 31.03.2026 · 40 (1) · 336-348
DOI: 10.1137/24m1706736 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 11.03.2026. Verfasst von Douglas Barnes und 4 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben. Gefördert von: Trinity College, University of Cambridge, Engineering and Physical Sciences Research Council, University of Cambridge.
Abstract (Originalsprache)
Let [Formula: see text] be a set of [Formula: see text] points in [Formula: see text], and suppose that the distance between each pair of points is revealed independently with probability [Formula: see text]. We study when this information is sufficient to reconstruct large subsets of [Formula: see text], up to isometry. Strong results for [Formula: see text] have been obtained by Girão et al. In this paper, we investigate higher dimensions, and show that if [Formula: see text], then we can reconstruct almost all of [Formula: see text] up to isometry, with high probability. We do this by relating it to a polluted graph bootstrap percolation result, for which we adapt the methods of Balogh, Bollobás, and Morris.
Förderung
- Trinity College, University of Cambridge
- Engineering and Physical Sciences Research Council
- University of Cambridge
- Cambridge Trust
- CMS Bursary
- Churchill College, University of Cambridge
Zitieren
APA
Barnes, D., Petr, J., Portier, J., Shaw, B. R., & Sergeev, A. (2026). Reconstructing Almost All of a Point Set in \(\boldsymbol{\mathbb{R}}\) d from Randomly Revealed Pairwise Distances. SIAM Journal on Discrete Mathematics, 40(1), 336-348. https://doi.org/10.1137/24m1706736
Vancouver
Barnes D, Petr J, Portier J, Shaw BR, Sergeev A. Reconstructing Almost All of a Point Set in \(\boldsymbol{\mathbb{R}}\) d from Randomly Revealed Pairwise Distances. SIAM Journal on Discrete Mathematics. 2026;40(1):336-348. doi:10.1137/24m1706736
BibTeX
@article{Barnes2026,
author = {Barnes, Douglas and Petr, Jan and Portier, Julien and Shaw, Benedict Randall and Sergeev, Alan},
title = {Reconstructing Almost All of a Point Set in \(\boldsymbol\mathbbR\) d from Randomly Revealed Pairwise Distances},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {1},
pages = {336--348},
doi = {10.1137/24m1706736}
}
EUVIMED