2
$\begingroup$

You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and rotation which set one-to-one correspondence between points in $A$ and points in $B$.

One can come up with following $O(n^2)$ algorithm. First of all, make a transition in such a way that centers of mass are matched. After that calculate convex hull of both sets. It will have $O(n)$ nodes. One can fix some edge from convex hull of $A$, then try to match it with all possible edges from convex hull of $B$ in $O(n)$ and check if it produces correct matching in another $O(n)$.

I suggest the following improvement to $O(n)$ which should work unless sets of points have some special kinds of symmetry. Consider inertia tensors of this set of points

$$I=\sum\limits_{i=1}^n\begin{pmatrix}x_i^2 & -2x_iy_i & -2x_i z_i \\ -2x_i y_i & y_i^2 & -2y_iz_i \\ -2x_iz_i & -2y_iz_i & z_i^2\end{pmatrix}$$

Since this is symmetric matrix, there is basis of its eigenvectors. Thus we can try to only match the main axes of inertia. This works find but only if all three eigenvalues are distinct. I assume there is also a way to solve the problem in the case when two eigenvalues coincide by reducing in to $2D$ case along the left axis but if all eigenvalues match there's nothing we can get from inertia tensor.

So, is it possible to avoid this issue with inertia tensor having same central main moments of inertia? And in general, are there any known algorithms to solve the problem in $o(n^2)$? Also are there any research considering this approach to solve the problem?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.