# Provably Approximated ICP

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 46 references that are in the map.
- First posted on arXiv 10 Jan 2021.

## Builds on (most cited first, 6 of 6)

- [Deep Closest Point: Learning Representations for Point Cloud Registration](https://mlsanity.com/paper/1905.03304/) (2019)
- [PointNetLK: Robust & Efficient Point Cloud Registration using PointNet](https://mlsanity.com/paper/1903.05711/) (2019)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration](https://mlsanity.com/paper/1904.02204/) (2019)
- [CoBe -- Coded Beacons for Localization, Object Tracking, and SLAM Augmentation](https://mlsanity.com/paper/1708.05625/) (2017)
- [Provable Approximations for Constrained ℓp Regression](https://mlsanity.com/paper/1902.10407/) (2019)

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

- [Multimodal Colored Point Cloud to Image Alignment](https://mlsanity.com/paper/2110.03249/) (2021)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)

## Abstract (arXiv)

The goal of the alignment problem is to align a (given) point cloud P = p1,cdots,pn to another (observed) point cloud Q = q1,cdots,qn. That is, to compute a rotation matrix R ∈ ℝ3 × 3 and a translation vector t ∈ ℝ3 that minimize the sum of paired distances sumi=1n D(Rpi-t,qi) for some distance function D. A harder version is the registration problem, where the correspondence is unknown, and the minimum is also over all possible correspondence functions from P to Q. Heuristics such as the Iterative Closest Point (ICP) algorithm and its variants were suggested for these problems, but none yield a provable non-trivial approximation for the global optimum. We prove that there always exists a "witness" set of 3 pairs in P × Q that, via novel alignment algorithm, defines a constant factor approximation (in the worst case) to this global optimum. We then provide algorithms that recover this witness set and yield the first provable constant factor approximation for the: (i) alignment problem in O(n) expected time, and (ii) registration problem in polynomial time. Such small witness sets exist for many variants including points in d-dimensional space, outlier-resistant cost functions, and different correspondence types. Extensive experimental results on real and synthetic datasets show that our approximation constants are, in practice, close to 1, and up to x10 times smaller than state-of-the-art algorithms.