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

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_i\bar 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 $n\ge2$, 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.

67 pages, 20 figures. Includes full proofs and experimental appendices

Computer Vision and Pattern Recognition (cs.CV); Computational Geometry (cs.CG); Machine Learning (cs.LG); Robotics (cs.RO); Optimization and Control (math.OC)

I.2.10; F.2.2; G.1.6

arXiv:2610.10408 [cs.CV]

(or arXiv:2610.10408v1 [cs.CV] for this version)

https://doi.org/10.48550/arXiv.2610.10408 arXiv-issued DOI via DataCite (pending registration)

From: Subhransu S. Bhattacharjee Mr. [view email] [v1] Wed, 7 Oct 2026 16:55:12 UTC (6,837 KB)