# Can a collection of points be recovered from its multiset of distances?

Consider $n$ distinct points $x_1,\dots,x_n$ on $\mathbb{R}$. Associated to these points is the multiset of all distances $d(x_i,x_j)$ between two points. Suppose one is only handed this multiset (you do not know the corresponding indices). Does this allow one to uniquely recover the original points up to reflection and translation?

-
By the way, this isn't graph theory (as indicated in the tags). –  Alexander Gruber Mar 3 '13 at 22:17
Uniquely up to reflection and translation is not very uniquely at all. Essentially the question is whether or not the equivalence relation "same multiset of distances" is the same equivalence relation as "same set up to a reflection and translation". –  Asaf Karagila Mar 3 '13 at 23:07
@Asaf: yes. What's your point? –  Qiaochu Yuan Mar 3 '13 at 23:08
@Qiaochu: And that's a much clearer way of phrasing the question. Saying "uniquely up to..." confused me for quite a few minutes, especially in light of Alexander's answer and the comments which follows it. –  Asaf Karagila Mar 3 '13 at 23:09
@Asaf: the original phrasing of the question was worse. I think your phrasing is unnecessarily pedantic. Perhaps we could say "if two such collections of points have the same multiset of distances, are they necessarily related by reflection and translation?" –  Qiaochu Yuan Mar 3 '13 at 23:11

This is a really nice question!

Counterexample for $n=6$

The sets $$\{0,1,4,5,11,13\}\\\{0,1,2,6,10,13\}$$ are affinely inequivalent, but the multiset of differences is in both cases $$1^2\cdot 2\cdot 3\cdot 4^2 \cdot 5 \cdot 6\cdot 7 \cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13.$$

Counterexamples for $n \geq 7$ According to Lemma 2.1 in the first linked article in the answer of Steve Kass, for all $n\geq 6$, a counterexample is given by $$X\cup \{n+1,n+3\}\quad\text{and}\quad X\cup\{2,n+1\}$$ where $X = \{5,6,7,\ldots,n-1,n-2\} \cup \{0,1,n,n+5\}$.

Uniqueness for $n\leq 5$

For $n\in\{1,2\}$, the uniqueness is clear.

Let $X = \{x_1,x_2,\ldots,x_n\}$ be a point set. We assume $x_1\leq x_2\leq\ldots \leq x_n$. Up to affine equivalence, we may assume $x_1 = 0$. We denote the distance of two points $x,y$ by $\delta(x,y) = \left|x-y\right|$ and furthermore define the abbreviation $\delta_{i,j} = \delta(x_i,x_j)$. In the multiset of distances, let $a \geq b\geq c\geq d$ be the largest elements. It is clear that $a = \delta_{1,n}$ and thus $x_n = a$. Up to affine equivalence, we may assume $b = \delta_{n-1,n}$ (the other possibility is $\delta_{1,2}$), so $x_{n-1} = b$. This shows the uniqueness for $n = 3$.

For $n=4$, $\{\delta_{1,2},\delta_{2,n}\} = \{c,x_4-c\}$. This distinquishes the last remaining distance $\delta_{2,3}$, which in turn fixes $x_2$.

It remains to consider the case $n=5$.

First we see that if one further point $x\in\{x_2,x_3\}$ is fixed, the set $X$ is completely determined: Let $y$ be the missing point. Among the four remaining distances $\delta(x_1,y)$, $\delta(x,y)$, $\delta(y,x_4)$, $\delta(y,x_5)$, the maximum $d_m$ is contained in the set $\{\delta(x_1,y),\delta(x_5,y)\} = \{d_m, x_5-d_m\}$. So we also know the set $\{\delta(x,y),\delta(y,x_4)\}$. Because of $x,y\in(x_0,x_4)$, $\delta(y,x_4)$ is the larger of those two distances, which fixes the point $y$.

By the choice of $c$, we have $c = \delta_{1,3}$ (Case A) or $c = \delta_{2,n}$ (Case B). If the multiset of distances admits only one of those two cases, then by the above reasoning, $X$ is uniquely determined. So we have to see that if both cases are possible, then the point sets are necessarily identical.

Case A) If $c = \delta_{1,3}$, then $x_3 = c$, and $d\in\{\delta_{1,2},\delta_{2,5}\}$.

Case A1) $d = \delta_{1,2}$. Now $X = \{0,d,c,b,a\}$, and the $10$ distances are $$\delta_{1,2} = d,\quad \delta_{1,3} = c,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = c-d,\quad \delta_{2,4} = b-d,\quad \delta_{2,5} = a-d,\\ \delta_{3,4} = b-c,\quad \delta_{3,5} = a-c, \\\delta_{4,5} = a-b$$

Case A2) $d = \delta_{2,5}$. Now $X = \{0,a-d,c,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-d,\quad \delta_{1,3} = c,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = -a+c+d,\quad \delta_{2,4} = -a+b+d,\quad \delta_{2,5} = d,\\ \delta_{3,4} = b-c,\quad \delta_{3,5} = a-c, \\\delta_{4,5} = a-b$$

Case B) If $c = \delta_{2,5}$, then $x_2 = a-c$, and $d\in\{\delta_{1,3},\delta_{3,5},\delta_{2,4}\}$.

Case B1) $d = \delta_{1,3}$. Now $X = \{0,a-c,d,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-c,\quad \delta_{1,3} = d,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = -a+c+d,\quad \delta_{2,4} = -a+b+c,\quad \delta_{2,5} = c,\\ \delta_{3,4} = b-d,\quad \delta_{3,5} = a-d, \\\delta_{4,5} = a-b.$$

By the above consideration, B1) and A1) cannot appear both (since they have $4$ points in common).

Assume that both B1) and A2) are possible. Then by comparing the distances, the two sets $\{-a+b+d, b-c\}$ and $\{-a+b+c, b-d\}$ must be the same. In both possibilities to match the elements, we end up with $c = d$, which shows that the point set is the same in both cases.

Case B2) $d = \delta_{3,5}$. Now $X = \{0,a-c,a-d,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-c,\quad \delta_{1,3} = a-d,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = c-d,\quad \delta_{2,4} = -a+b+c,\quad \delta_{2,5} = c,\\ \delta_{3,4} = -a+b+d,\quad \delta_{3,5} = d, \\\delta_{4,5} = a-b.$$ We go on similarly as in B1).

Case B3) $d = \delta_{2,4}$. Here necessarily $a+d = b+c$, and the point $x_3$ is not yet fixed. The point set is $X = \{0,a-c,x_3,b,a\}$. We go on similarly as in B1), B2) to see that if B3) occurs together with A1) or A2), then $X$ is uniquely determined.

EDIT: The uniqueness for $n\leq 5$ is also stated in Lemma 2.1. in the first linked article of Steve Kass. However, the proof doesn't give to many details, and I do not understand the part "since $a + b = c$, if $a + c = 1$ then $b$ uniquely determines $T$.".

-
Nicely done! Thank you. –  Lepidopterist Mar 3 '13 at 23:38
Very good. I'm glad it's not true, since I couldn't prove it! I wonder if $n=6$ is the smallest counterexample. –  Alexander Gruber Mar 3 '13 at 23:40
Awesome answer. I'll leave the bounty up so this gets a few days in the spotlight before I award. –  Alexander Gruber Mar 14 '13 at 16:00
@AlexanderGruber: Thanks. Frankly speaking, I consider the answer awesome for $n=6$ and $n\leq 4$, but not for $n=5$. There are just too many unpleasant cases, and I didn't discuss them all in detail. Any idea on further reducing the complexity would be welcome. My hope is that with further simplifications, a discussion of the case $n=6$ would become feasible (resulting in a classification of the counterexamples). So yes, leave the bounty up and let's hope this gets some more attention. –  azimut Mar 14 '13 at 16:23
Is it clear that there exist counter-examples for all $n>6$? I can't think of a simple way to extend this counter-example to larger values of $n$. Might it be possible that there are larger values of $n$ where $n$ points can be recovered from their multiset? –  Jared Mar 18 '13 at 23:40

This problem is called the "turnpike problem" or the "partial digest problem." Sets like the two @azimut gave are called "homometric" or "homeometric," and there can be many for a given set of distances (but the number of them is always a power of two). Here are a couple of references:

Reconstructing Sets From Interpoint Distances

The Partial Digest Problem

On the Turnpike Problem

-
Wow, great resources. –  Lepidopterist Mar 3 '13 at 23:43