Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
Rubix achieves global correspondence-free planar point set alignment by reformulating the problem as finding the farthest vertex of the permutation polygon, the convex hull of complex correlations. This approach guarantees optimality under squared Euclidean loss and resolves Rote's rotation-assignment open problem by proving a sharp bound on the polygon's vertices. The method extends to 3D and partial matching via branch-and-bound, demonstrating significant speedups and accuracy improvements over existing techniques on real-world datasets.
Global point set alignment is solved exactly by finding the farthest vertex of a novel "permutation polygon," resolving a long-standing open problem in assignment geometry.
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\bar 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\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.