Convergence characteristics of the ICP algorithm
The point-set registration problem seeks the transformation that optimally aligns a point set A to a reference point set B, and has numerous applications in computer graphics, computer vision, and robotics. Proposed by Besl and McKay, the iterative closest point (ICP) algorithm has seen wide adoption as a heuristic solution to this problem, with good performance in practice. In this bachelor's thesis we review and illustrate results from the literature about the convergence characteristics of ICP, focusing primarily on complexity bounds. We first explain in detail some of the results by Ezra, Sharir, and Efrat that bound the number of iterations performed by the algorithm, and then explore work by Arthur and Vassilvitskii that improve on the earlier results. In the process we build an intuition for geometric properties of the algorithm on which the presented ICP point configurations used to prove the complexity bounds rely. Finally, we propose a tool for exploratory analysis by creating convergence diagrams that visualise the final cost value the ICP algorithm converges on when run on (A + t0, B), for initial offsets t0 on a grid of arbitrary resolution.