For context, this result would be useful in carrying out practical attacks on this problem using this idea.
I have tested this numerically and seems to work so often for me that I think it should be provable:
If I have 3 points in 2 dimensions which fulfill a distance equation with distance matrix:
$$D = \begin{bmatrix}0&d(p_1,p_2)&d(p_1,p_3)\\d(p_2,p_1)&0&d(p_2,p_3)\\d(p_3,p_1)&d(p_3,p_2)&0\end{bmatrix}$$
so that $$d(a,b)=<a,b>$$ with known $d(p_i,p_j)$ and $<a,b>$ being normal euclidean distance between $a$ and $b$. Can I prove that solution will be unique up to
- translation + rotation
- translation + reflection
How to prove that for two such given sets of 3 points fulfilling distance equations, one of those transformation between the sets can be found?
Best Answer
I am not a mathematician, and I do not normally do proofs, as I only use math as a tool to find solutions to existing problems. So, rather than show the proof, I show how to construct the actual rotation matrix and translation vector for arbitrary 3D point triplets with positive pairwise distances.
(I hope one of the mathematicians here can show how to condense this into a proper proof, as a separate answer.)
When you have three points $$\bbox{ \vec{p}_1 = \left [ \begin{matrix} x_1 \\ y_1 \\ z_1 \end{matrix} \right ] }, \quad \bbox{ \vec{p}_2 = \left [ \begin{matrix} x_2 \\ y_2 \\ z_2 \end{matrix} \right ] }, \quad \bbox{ \vec{p}_3 = \left [ \begin{matrix} x_3 \\ y_3 \\ z_3 \end{matrix} \right ] }$$ with positive pairwise distances $$\begin{aligned} d_{12} &= \left\lVert\vec{p}_2 - \vec{p}_1\right\rVert = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2} \\ d_{13} &= \left\lVert\vec{p}_3 - \vec{p}_1\right\rVert = \sqrt{(x_3 - x_1)^2 + (y_3 - y_1)^2 + (z_3 - z_1)^2} \\ d_{23} &= \left\lVert\vec{p}_3 - \vec{p}_2\right\rVert = \sqrt{(x_3 - x_2)^2 + (y_3 - y_2)^2 + (z_3 - z_2)^2} \\ \end{aligned}$$ you can construct a coordinate system where $\vec{p}_1$ is at origin, $\vec{p}_2$ is on the positive $x$ axis, and $\vec{p}_3$ is on the $xy$ plane on the positive $y$ side; i.e. $$\bbox{ \vec{p}_1^\prime = \left [ \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right ] }, \quad \bbox{ \vec{p}_2^\prime = \left [ \begin{matrix} d_{12} \\ 0 \\ 0 \end{matrix} \right ] }, \quad \bbox{ \vec{p}_3^\prime = \left [ \begin{matrix} u \\ v \\ 0 \end{matrix} \right ] }$$ where $$\bbox{\left\lbrace \; \begin{aligned} u^2 + v^2 &= d_{13}^2 \\ (d_{12} - u)^2 + v^2 &= d_{23}^2 \end{aligned}\right .} \quad \iff \quad \bbox{ \left\lbrace \; \begin{aligned} \displaystyle u &= \frac{d_{12}^2 + d_{13}^2 - d_{23}^2}{2 d_{12}} \\ \displaystyle v &= \sqrt{d_{13}^2 - u^2} \\ \end{aligned} \right .}$$ We can describe this transformation using an orthonormal matrix $\mathbf{M}$ and translation vector $\vec{t}$ as $$\bbox{ \vec{p}^\prime = \mathbf{M} \left(\vec{p} - \vec{p}_1 \right) = \mathbf{M}\vec{p} + \vec{t} }$$ where $$\bbox{ \vec{t} = -\mathbf{M} \vec{p}_1 }$$ and $$\bbox{ \mathbf{M} = \left [ \begin{matrix} m_{11} & m_{12} & m_{13} \\ m_{21} & m_{22} & m_{23} \\ m_{31} & m_{32} & m_{33} \end{matrix} \right ]} , \quad \bbox{ \hat{u} = \left [ \begin{matrix} m_{11} \\ m_{12} \\ m_{13} \end{matrix} \right ]} , \quad \bbox{ \hat{v} = \left [ \begin{matrix} m_{21} \\ m_{22} \\ m_{23} \end{matrix} \right ]} , \quad \bbox{ \left [ \begin{matrix} m_{31} \\ m_{32} \\ m_{33} \end{matrix} \right ] = \hat{u} \times \hat{v} }$$ with $$\bbox{ \left\lVert\hat{u}\right\rVert = \left\lVert\hat{v}\right\rVert = 1 }, \quad \bbox{ \hat{u} \cdot \hat{v} = 0 }, \quad \bbox{ \hat{u} = \frac{\vec{p}_2 - \vec{p}_1}{\left\lVert\vec{p}_2 - \vec{p}_1\right\rVert } }, \quad \bbox{ \hat{v} = \frac{\vec{p}_3 - \vec{p}_1 - \hat{u} \left( \hat{u} \cdot \left ( \vec{p}_3 - \vec{p}_1 \right ) \right )}{\left\lVert \vec{p}_3 - \vec{p}_1 - \hat{u} \left( \hat{u} \cdot \left ( \vec{p}_3 - \vec{p}_1 \right ) \right ) \right\rVert} }$$ If we examine the matrix $\mathbf{M}$, we observe that it is orthonormal with determinant 1, and therefore a pure rotation matrix.
This means that if we have two such point triplets $\vec{p}_i$ and $\vec{q}_i$ with the same pairwise distance, and their corresponding rotation matrices $\mathbf{M}_1$ and $\mathbf{M}_2$, we find that $$\mathbf{M}_1 ( \vec{p}_i - \vec{p}_1 ) = \mathbf{M}_2 ( \vec{q}_i - \vec{q}_1 )$$ because their transformed coordinates ($(0, 0, 0)$, $(d_{12}, 0, 0)$, and $(u, v, 0)$) are the same if their pairwise distances are the same. Reordering the terms we see that $$\vec{p}_i = \mathbf{M}_1^{-1} \mathbf{M}_2 \vec{q}_i + \vec{p}_1 - \mathbf{M}_1^{-1} \mathbf{M}_2 \vec{q}_1$$ which can be written as $$\vec{p}_i = \mathbf{R} \vec{q}_i + \vec{r}$$ where $$\bbox{ \mathbf{R} = \mathbf{M}_1^{-1} \mathbf{M}_2 }, \quad \bbox{ \vec{r} = \vec{p}_1 - \mathbf{R} \vec{q}_1 }$$ Thus, we have constructed the rotation matrix $\mathbf{R}$ and translation vector $\vec{r}$. Hopefully, its existence is proof enough.
Note that the above case is for the rotation only. However, if you change the third row vector of $\mathbf{M}$ into $\hat{v} \times \hat{u} = -\hat{u} \times \hat{v}$, its determinant will be -1, so it will be an "improper rotation matrix": a reflection.