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 P4(x,y,z)=n∑l=1((x−xl)2+(y−yl)2+(z−zl)2)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
where Aijk is obtained as the sum over all points (xl,yl,zl) from the initial set. To find the permutation, it is enough to calculate P4 for all points in both sets and them match points with the same index after they were sorted by the corresponding P4 value.
It is tempting to try the same trick with P2(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 rk=(xk,yk,zk). 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 rk to the axis r is expressed as
The numerator here is a quadratic form, hence can be rewritten as
Correspondingly, the sum of squared distances for k=1..n is defined by the quadratic form
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:
Here I1, I2 and I3 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 I1=I2=I3.
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 I2 and I3 by x2. 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.