Vrftsjtryk

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)&0end{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

1. translation + rotation


2. 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?

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} &= leftlVertvec{p}_2 - vec{p}_1rightrVert = sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2} \
d_{13} &= leftlVertvec{p}_3 - vec{p}_1rightrVert = sqrt{(x_3 - x_1)^2 + (y_3 - y_1)^2 + (z_3 - z_1)^2} \
d_{23} &= leftlVertvec{p}_3 - vec{p}_2rightrVert = 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{leftlbrace ; 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{ leftlbrace ; 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{ leftlVerthat{u}rightrVert = leftlVerthat{v}rightrVert = 1 },
quad
bbox{ hat{u} cdot hat{v} = 0 }, quad
bbox{ hat{u} = frac{vec{p}_2 - vec{p}_1}{leftlVertvec{p}_2 - vec{p}_1rightrVert } }, 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 )}{leftlVert vec{p}_3 - vec{p}_1 - hat{u} left( hat{u} cdot left ( vec{p}_3 - vec{p}_1 right ) right ) rightrVert} }$$
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.