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 σ of two centered n-point sets defines a complex correlation zσ=∑ix̅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 𝒪(n5) 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.
Related
- A Cartan geometry from a correspondence space in Riemannian geometry
- Global regularity for the unidirectional Euler-alignment system with supercritical dissipation
- The Geometry of Updates: Fisher Alignment at Vocabulary Scale
- Negative Results for Reciprocity-Based Over-the-Air Split Learning Under Channel Aging: Stability, Alignment, and Geometry
- Conformal tetrahedra and global rigidity of sphere packings in constant curvature background geometry
BibTeX
@misc{bhattacharjee2026rubix,
title = {{Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry}},
author = {Subhransu S. Bhattacharjee and Dylan Campbell and Rahul Shome},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10408},
eprint = {2610.10408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10408},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
AU - Subhransu S. Bhattacharjee
AU - Dylan Campbell
AU - Rahul Shome
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10408
UR - https://arxiv.org/abs/2610.10408
AB - 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_σ=∑_ix̅_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 𝒪(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.
ER -