# 3D-BBS: Global Localization for 3D Point Cloud Scan Matching Using Branch-and-Bound Algorithm

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2023.

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

- [KISS-Matcher: Fast and Robust Point Cloud Registration Revisited](https://mlsanity.com/paper/2409.15615/) (2024)
- [BUFFER-X: Towards Zero-Shot Point Cloud Registration in Diverse Scenes](https://mlsanity.com/paper/2503.07940/) (2025)
- [Toward Zero-Shot Point Cloud Registration Across Diverse Scales, Scenes, and Sensor Setups](https://mlsanity.com/paper/2601.02759/) (2026)
- [BEV-SLD: Self-Supervised Scene Landmark Detection for Global Localization with LiDAR Bird's-Eye View Images](https://mlsanity.com/paper/2603.17159/) (2026)
- [Towards Global Localization using Multi-Modal Object-Instance Re-Identification](https://mlsanity.com/paper/2409.12002/) (2024)
- [SANDRO: a Robust Solver with a Splitting Strategy for Point Cloud Registration](https://mlsanity.com/paper/2503.07743/) (2025)
- [GMOR: A Lightweight Robust Point Cloud Registration Framework via Geometric Maximum Overlapping](https://mlsanity.com/paper/2508.17427/) (2025)
- [S-BEVLoc: BEV-based Self-supervised Framework for Large-scale LiDAR Global Localization](https://mlsanity.com/paper/2509.09110/) (2025)

## Abstract (arXiv)

This paper presents an accurate and fast 3D global localization method, 3D-BBS, that extends the existing branch-and-bound (BnB)-based 2D scan matching (BBS) algorithm. To reduce memory consumption, we utilize a sparse hash table for storing hierarchical 3D voxel maps. To improve the processing cost of BBS in 3D space, we propose an efficient roto-translational space branching. Furthermore, we devise a batched BnB algorithm to fully leverage GPU parallel processing. Through experiments in simulated and real environments, we demonstrated that the 3D-BBS enabled accurate global localization with only a 3D LiDAR scan roughly aligned in the gravity direction and a 3D pre-built map. This method required only 878 msec on average to perform global localization and outperformed state-of-the-art global registration methods in terms of accuracy and processing speed.