Reconstructing a point set from a random subset of its pairwise distances
classification
🧮 math.CO
math.MG
keywords
pairwiserandomreconstructingdistancesresultthresholdbenjaminidistance
read the original 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 = (\log n)/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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.