Determining a Points Configuration on the Line from a Subset of the Pairwise Distances

Itai Benjamini, Elad Tzalik

Published 2022-08-29Version 1

We consider rigidity type problems on $\mathbb{R}, S^1$ in a non-generic setting. Given $n$ distinct points $V = \{ v_1,...,v_n \}$ and a set of mutual distances $\mathcal{P} \subseteq { V \choose 2}$, does $\mathcal{P}$ defines the position of $V$ uniquely up to isometry? We show that if $|\mathcal{P}| =\Omega(n^{3/2})$, one can determine the position of a subset $V' \subseteq V$, $|V'| = \Omega(\frac{|\mathcal{P}|}{n})$. The main ingredient in the proof is showing that dense graphs $G=(V,E)$ for which every two non-adjacent vertices have only a few common neighbours must have large cliques. We also consider random distance set $\mathcal{P}$. If the distance of each pair of points is known with probability $p = \frac{C \ln(n)}{n}$ for large enough $C$ then it is possible to reconstruct $V$ from the distances w.h.p. and provide a randomized algorithm with linear expected running time that returns an embedding to the line w.h.p.