Inequality of Euclidean Distances in Aligning Point Clouds

Question

A, B, C are each a sequence of n points in ordinary 3D space.

The squared Eudlidean distance between i^th point of A and the i^th point of B is: $$ d(\vec{a}_i, \vec{b}_i) = (a_{ix} - b_{ix})^2 + (a_{iy} - b_{iy})^2 + (a_{iz} - b_{iz})^2 $$

The sum of squared Euclidean distance between corresponding points of A and B is:

$$ d(A, B) = \sum_{i = 0}^{n-1} d(\vec{a}_i, \vec{b}_i) $$

Define the least sum of squared Euclidean distance A and B, $ \Delta(A, B) $, as the least d(A, B) under all possible reordering of the sequence of points in B. [Updated after quasi gives a counter example when the points are not allowed to reorder]

A new sequence of points C_A can be formed by rotating, translating, and reordering C to minimize $ \Delta(A, C) $. Similarly, we can create another sequence of points C_B. (This is translating & rotating a 3D object so that it best matches another 3D object).

Is $ \Delta(C_{A}, C_{B}) \ge \Delta(A, B) $ always true for all possible A, B, and C?

Answer 1

As stated, it's false.

We can stay on the real line (i.e., $A,B,C$ will be sequences of real numbers).

Let $n=2$, and let \begin{align*} A&=-3,-1\\[4pt] B&=3,\;1\\[4pt] C&=0,\;0\\[4pt] \end{align*} Then \begin{align*} C_A&=-2,-2\\[4pt] C_B&=\;\;2,\;2\\[4pt] \end{align*} but $$\Delta(C_{A}, C_{B}) = 32 < 40 = \Delta(A, B)$$ The above counterexample was based on the conditions originally specified.

But with the updated conditions, it's still false.

In the plane, with $n=3$, let \begin{align*} A&=(-2,0),\;(-12,0),\;(-12,24)\\[4pt] B&=(+2,0),\;(+12,0),\;(+12,24)\\[4pt] C&=(0,0),\;(0,0),\;(0,0)\\[4pt] \end{align*} Then \begin{align*} C_A&=(-7,12),\;(-7,12),(-7,12)\\[4pt] C_B&=(+7,12),\;(+7,12),(+7,12)\\[4pt] \end{align*} but $$\Delta(C_{A}, C_{B}) = (3)(14^2) = 588$$ $$\Delta(A, B) = (2)(14^2) + 24^2 = 968$$