# Given the pairwise distances between $n$ points, how can I find plausible coordinates for the points?

If I have three points $A, B, C$, and I know the distances between $A$ and $B$, $B$ and $C$, and $A$ and $C$,

(1) How can I find (one possible value for) the coordinates of $A$, $B$, and $C$?

(2) If the distance function is a viable distance metric, must a solution always exist?

(3) How can I generalize this to $n$ points?

-
If your question is about embeddability into $\mathbb{R}^n$ with the Euclidean metric, then see mathoverflow.net/questions/12394/… . – Qiaochu Yuan Aug 10 '12 at 21:58
Are the points in ${\mathbb R}^3$? – leonbloy Aug 10 '12 at 22:36

Because the distances do not change with translations, reflection and rotations, we can (even if we are in 3D) restrict to the $x,y$ plane, and fix $A=(0,0)$ , $B=(b_1,0)$, $C=(c_1,c_2)$

Then $b_1 = d_{AB}$. Also, $c_1^2 + c_2^2 = d_{AC}^2$ and $(c_1-b_1)^2 + c_2^2 = d_{BC}^2$

This gives: $$c_1 = \frac{d_{AC}^2 - d_{BC}^2 + d_{AB}^2}{2 d_{AB}}$$

and

$$c_2^2 = d_{AC}^2 - c_1^2$$

which must be positive to have a solution (well, two). From this we get the general points by rotations, translations and reflections. I'm not sure if there is a more elegant or generalizable way.

-

Denote the distances $AB, BC, AC$ as $p,q,r$ respectively. Let's work in $\mathbb R^n$, with the Euclidean Metric.

Place $A$ at the origin $(0,0,0,\cdots,0)$, without loss of generality. Place $B$ on the positive $x_1$-axis at the known distance from $A$.So, it's coordinates are $(p,0, \cdots ,0)$

Let the coordinates of $C$ be $(x_1,x_2 \cdots, x_n)$. Then we have the equations $$\sum_{i=1}^n x_i^2=r^2, \text{ and } (x_1- p)^2+\sum_{i=2}^nx_i^2=q^2,$$ from the distances we know and the usual euclidean distance formula in $\mathbb R^n$.

Some algebra reduces this to the single equation $(x_1- p)^2 +r^2-x_1^2=q^2$ and so, $x_1 = \frac{p^2+q^2-r^2}{2p}$.

In $2$-dimensions, you get two values for the y-coordinate, one above the $x$-axis and one below it. But in higher dimensions, after substituting the value of $x_1$ (That we just determined) into $\sum_{i=1}^n x_i^2=r^2$, this yields the locus of all possible locations for the third point $C$. After this, all translations, rotations and reflections( Which are represented by invertible$n \times n$ matrices), yields all possible embeddings (Or placements) of the triangle in $\mathbb R ^n$.

-