Uniqueness of point placement with the knowledge of interdistances

Question

I was wondering if anybody can help in this seemingly weird problem. Consider a set of points $x_1, \ldots, x_n$ such that $x_1 = -a$, $x_n=a$, and $-a<x_i<a$ for $i \in \{2,3,\ldots,n-1\}$. Given a set of numbers $\mathcal{D} = \{ |x_i - x_j|, \forall i\neq j\}$ that is the set of interdistances between all the points.

Notes to clarify more on $\mathcal{D}$:

1. We only have the numbers in $\mathcal{D}$, we do not know which number corresponds to the distance of which two points.
2. The maximum distance in $\mathcal{D}$ is always $2a$, which is the distance between the extremes $x_1$ and $x_n$.
3. For each point $x_i, i \in \{2,..,n-1\}$, there will exist two numbers in $\mathcal{D}$ which will add up to $2a$, those are the distances from this point to the extremes.
4. The cardinality of $\mathcal{D}$ is always $^nC_2$, which means that all distances between the points are distinct.

Suppose that we could find a placement (the values) for the points $x_2, \ldots, x_{n-1}$ for which the interdistances form the set $\mathcal{D}$, it is obvious that $-x_2, \ldots, -x_{n-1}$ will result in the same set $\mathcal{D}$.

The objective is to prove (or disprove) that there are no other set of values for $x_2,\ldots, x_{n-1}$ for which their set of interdistances (call it $\mathcal{D}_2$) is equivalent to $\mathcal{D}$.

In other words, given the set of interdistances between some points on a line (between $-a$ and $a$), can we uniquely determine the values of these points, up to the ambiguity of reflection?

This is a little similar to the point placement problem in computer science, except that the distances are all known exactly, but not known to which pairs they belong.

Answer 1

The is called the turnpike reconstruction problem in this paper:

Skiena, Steven S., Warren D. Smith, and Paul Lemke. "Reconstructing sets from interpoint distances." Proceedings 6th Symposium on Computational Geometry. ACM, 1990. Later published in Discrete and Computational Geometry. Springer. Berlin, Heidelberg, 2003. 597-631. Springer link.

They provide a worst-case exponential algorithm which nevertheless runs fast under probabilistic assumptions, and proved many variants NP-hard. You might use Google Scholar to browse through the more than 50 papers that later cited this seminal paper. Sets of points that have more than one valid reconstruction are called homometric.