pith. sign in

arxiv: 2301.11019 · v1 · pith:3GB7FX46new · submitted 2023-01-26 · 🧮 math.CO · math.MG

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

classification 🧮 math.CO math.MG
keywords pairwiserandomreconstructingdistancesresultthresholdbenjaminidistance
0
0 comments X
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.