Reconstructing a point set from a random subset of its pairwise distances

MaRDI QIDQ6424446zbMATH OpenFDO

Authors António Girão, Freddie Illingworth, Lukas Michel, Emil Powierski, Alex Scott

Publication date 26 January 2023

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $V$ be a set of $n$ points on the real line. Suppose that each pairwise distance is known independently with probability $p$. How much of $V$ can be reconstructed up to isometry? We prove that $p=(logn)/n$ is a sharp threshold for reconstructing all of $V$ which improves a result of Benjamini and Tzalik. This follows from a hitting time result for the random process where the pairwise distances are revealed one-by-one uniformly at random. We also show that $1/n$ is a weak threshold for reconstructing a linear proportion of $V$.

This page was built for publication: Reconstructing a point set from a random subset of its pairwise distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6424446)