EUVIMEDEUVIMED entdecken
Crossref

Reconstructing Almost All of a Point Set in \(\boldsymbol{\mathbb{R}}\) d from Randomly Revealed Pairwise Distances

Douglas Barnes, Jan Petr, Julien Portier, Benedict Randall Shaw, Alan Sergeev

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →