# Consensus Maximization Tree Search Revisited

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

## Key facts

- Cited by 10 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 6 Aug 2019.

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

- [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021)
- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [Accelerating Globally Optimal Consensus Maximization in Geometric Vision](https://mlsanity.com/paper/2304.05156/) (2023)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023)
- [Space-Partitioning RANSAC](https://mlsanity.com/paper/2111.12385/) (2021)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Unsupervised Learning for Robust Fitting:A Reinforcement Learning Approach](https://mlsanity.com/paper/2103.03501/) (2021)
- [Consensus Maximisation Using Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2103.04200/) (2021)
- [Maximum Consensus by Weighted Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2112.00953/) (2021)

## Abstract (arXiv)

Consensus maximization is widely used for robust fitting in computer vision. However, solving it exactly, i.e., finding the globally optimal solution, is intractable. A* tree search, which has been shown to be fixed-parameter tractable, is one of the most efficient exact methods, though it is still limited to small inputs. We make two key contributions towards improving A* tree search. First, we show that the consensus maximization tree structure used previously actually contains paths that connect nodes at both adjacent and non-adjacent levels. Crucially, paths connecting non-adjacent levels are redundant for tree search, but they were not avoided previously. We propose a new acceleration strategy that avoids such redundant paths. In the second contribution, we show that the existing branch pruning technique also deteriorates quickly with the problem dimension. We then propose a new branch pruning technique that is less dimension-sensitive to address this issue. Experiments show that both new techniques can significantly accelerate A* tree search, making it reasonably efficient on inputs that were previously out of reach.