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

arXiv:2610.10408 · cs.CV, cs.CG, cs.LG, cs.RO, math.OC · Submitted 2026-10-07 · Read on arXiv

cs.CV, cs.CG, cs.LG, cs.RO, math.OC

Submitted: 2026-10-07

Updated: 2026-10-07

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

Code: https://github.com/url-kaist/Quatro

License: http://creativecommons.org/licenses/by/4.0/

The gist: Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions.

Terminology

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 σ of two centered n-point sets defines a complex correlation z σ= sum i x i y σ(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 2, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in 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.

Sources

Related papers