Rotational invariants in geometry

Правка en3, от adamant, 2022-02-12 16:28:55

Hi everyone!

Today I'd like to write about some polynomials which are invariant under the rotation and relabeling in euclidean spaces. Model problems work with points in the 3D space, however both ideas, to some extent, might be generalized for higher number of dimensions. They might be useful to solve some geometric problems under the right conditions. I used some ideas around them in two problems that I set earlier.

Congruence check in random points

You're given two set of lines in 3D space. The second set of lines was obtained from the first one by the rotation and relabeling. You're guaranteed that the first set of lines was generated uniformly at random on the sphere, find the corresponding label permutation.

Actual problem: 102354F - Cosmic Crossroads.

Solution

Let $$$P_4(x, y, z) = \sum\limits_{l=1}^n \left((x-x_l)^2+(y-y_l)^2 + (z-z_l)^2\right)^2$$$. It is a fourth degree polynomial, which geometric meaning is the sum of distances from $$$(x, y, z)$$$ to all points in the set, each distance raised to power $$$4$$$. Distance is preserved under rotation, hence this expression is invariant under rotation transform. On the other hand it may be rewritten as

$$$P_4(x, y, z) = \sum\limits_{i=0}^4 \sum\limits_{j=0}^4 \sum\limits_{k=0}^4 A_{ijk} x^i y^j z^k,$$$

where $$$A_{ijk}$$$ is obtained as the sum over all points $$$(x_l,y_l,z_l)$$$ from the initial set. To find the permutation, it is enough to calculate $$$P_4$$$ for all points in both sets and them match points with the same index after they were sorted by the corresponding $$$P_4$$$ value.

It is tempting to try the same trick with $$$P_2(x, y, z)$$$, but it is the same for all the points in the set.

Burunduk1 taught me this trick after the Petrozavodsk camp round which featured the model problem.

Sum of distances to the line passing through the origin

You're given a set of points $$$r_k=(x_k, y_k, z_k)$$$. A torque needed to rotate the system of points around the axis $$$r=(x, y, z)$$$ is proportional to the sum of squared distances to the axis across all points. What is the minimum number of points you need to find the minimum amount of points that have to be added to the set, so that the torque needed to rotate it around any axis is exactly the same.

Actual problem: Hackerrank — The Axis of Awesome

Solution

The squared distance from the point $$$r_k$$$ to the axis $$$r$$$ is expressed as

$$$\dfrac{|r_k \times r|^2}{r \cdot r} = \dfrac{(y_k z - z_k y)^2+(x_k z - z_k x)^2+(x_k y - y_k x)^2}{x^2+y^2+z^2}.$$$

The numerator here is a quadratic form, hence can be rewritten as

$$$|r_k \times r|^2 = \begin{pmatrix}x & y & z\end{pmatrix} \begin{pmatrix} y_k^2 + z_k^2 & -x_k y_k & -x_k z_k \\ -x_k y_k & x_k^2 + z_k^2 & -y_k z_k \\ -x_k z_k & -y_k z_k & x_k^2 + y_k^2 \end{pmatrix} \begin{pmatrix}x \\ y \\ z\end{pmatrix}.$$$

Correspondingly, the sum of squared distances for $$$k=1..n$$$ is defined by the quadratic form

$$$I = \sum\limits_{k=1}^n\begin{pmatrix} y_k^2 + z_k^2 & -x_k y_k & -x_k z_k \\ -x_k y_k & x_k^2 + z_k^2 & -y_k z_k \\ -x_k z_k & -y_k z_k & x_k^2 + y_k^2 \end{pmatrix},$$$

known in analytic mechanics as the inertia tensor. As any other tensor, its coordinate form is invariant under rotation.

Inertia tensor is a positive semidefinite quadratic form, hence there is an orthonormal basis in which it is diagonal:

$$$I = \begin{pmatrix}I_1 & 0 & 0 \\ 0 & I_2 & 0 \\ 0 & 0 & I_3\end{pmatrix}.$$$

Here $$$I_1$$$, $$$I_2$$$ and $$$I_3$$$ are the eigenvalues of $$$I$$$, also called the principal moments of inertia (corresponding eigenvectors are called the principal axes of inertia). From this representation we deduce that the condition from the statement is held if and only if $$$I_1 = I_2 = I_3$$$.

Adding a single point on a principal axis would only increase principal moments on the other axes. For example, adding $$$(x, 0, 0)$$$ would increase $$$I_2$$$ and $$$I_3$$$ by $$$x^2$$$. Knowing this, one can prove that the answer to the problem is exactly $$$3-m$$$ where $$$m$$$ is the multiplicity of the smallest eigenvalue of $$$I$$$.

Applying it to the first problem

Now, another interesting observation about inertia tensor is that both principal inertia moments and principal inertia axes would be preserved under rotation. It means that in the first problem, another possible way to find the corresponding rotation and the permutation of points is to find principal inertia axes for both sets of points and then find a rotation that matches corresponding principal inertia axes in the first and the second sets of points.

Unfortunately, this method still requires that principal inertia moments are all distinct (which generally holds for random sets of points), otherwise there would be an infinite amount of eigendecompositions of $$$I$$$.

Теги tutorial, geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский adamant 2022-02-13 13:45:42 911
en7 Английский adamant 2022-02-12 16:40:09 7
en6 Английский adamant 2022-02-12 16:36:02 14
en5 Английский adamant 2022-02-12 16:34:20 27
en4 Английский adamant 2022-02-12 16:30:03 39
en3 Английский adamant 2022-02-12 16:28:55 1
en2 Английский adamant 2022-02-12 06:05:28 1
en1 Английский adamant 2022-02-12 05:27:52 5074 Initial revision (published)