Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

arXiv:2610.10408v1 Announce Type: new Abstract: Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching sigma of two centered n-point sets defines a complex correlation z_sigma=sum_iar x_i y_{sigma(i)}. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of n(n-1) vertices for nge2, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in mathcal O(n^5) operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

Source: arXiv cs.CV | 2026-10-08