{
  "id": "2208.13855",
  "version": "v1",
  "published": "2022-08-29T19:53:09.000Z",
  "updated": "2022-08-29T19:53:09.000Z",
  "title": "Determining a Points Configuration on the Line from a Subset of the Pairwise Distances",
  "authors": [
    "Itai Benjamini",
    "Elad Tzalik"
  ],
  "categories": [
    "math.MG",
    "math.CO",
    "math.PR"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-29T19:53:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "points configuration",
      "pairwise distances",
      "rigidity type problems",
      "random distance set",
      "determining"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}