Illingworth, Frederick;
Girao, Antonio;
Michel, Lukas;
Powierski, Emil;
Scott, Alex;
(2024)
Reconstructing a point set from a random subset of its pairwise distances.
SIAM Journal on Discrete Mathematics
, 38
(4)
pp. 2709-2720.
10.1137/23M1586860.
Preview |
Text
Submission.pdf - Accepted Version Download (225kB) | Preview |
Abstract
Let V be a set of n points on the real line. Suppose that each pairwise distance isknown independently with probability p. How much of V can be reconstructed up to isometry? Weprove that p = (log n)/n is a sharp threshold for reconstructing all of V , which improves a resultof Benjamini and Tzalik. This follows from a hitting time result for the random process where thepairwise distances are revealed one by one uniformly at random. We also show that 1/n is a weakthreshold for reconstructing a linear proportion of V.
| Type: | Article |
|---|---|
| Title: | Reconstructing a point set from a random subset of its pairwise distances |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/23M1586860 |
| Publisher version: | https://doi.org/10.1137/23M1586860 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10197629 |
Archive Staff Only
 |
View Item |
