# Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration

arXiv: https://arxiv.org/abs/1904.02204 · HTML: https://mlsanity.com/paper/1904.02204/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2019.

## Built on by (most cited first, 6 of 6)

- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Complete Neural Networks for Complete Euclidean Graphs](https://mlsanity.com/paper/2301.13821/) (2023)
- [Provably Approximated ICP](https://mlsanity.com/paper/2101.03588/) (2021)
- [Toward bilipshiz geometric models](https://mlsanity.com/paper/2511.11735/) (2025)
- [Symmetrized Robust Procrustes: Constant-Factor Approximation and Exact Recovery](https://mlsanity.com/paper/2207.08592/) (2022)

## Abstract (arXiv)

In recent years, several branch-and-bound (BnB) algorithms have been proposed to globally optimize rigid registration problems. In this paper, we suggest a general framework to improve upon the BnB approach, which we name Quasi BnB. Quasi BnB replaces the linear lower bounds used in BnB algorithms with quadratic quasi-lower bounds which are based on the quadratic behavior of the energy in the vicinity of the global minimum. While quasi-lower bounds are not truly lower bounds, the Quasi-BnB algorithm is globally optimal. In fact we prove that it exhibits linear convergence -- it achieves ε-accuracy in ~O(log(1/ε))  time while the time complexity of other rigid registration BnB algorithms is polynomial in 1/ε . Our experiments verify that Quasi-BnB is significantly more efficient than state-of-the-art BnB algorithms, especially for problems where high accuracy is desired.