For many applications ranging from computational structural biology to surface reconstruction, aligning two point clouds under rigid motions to minimize the root mean squared (RMS) distance appears as a central problem. In practice, some variation of the iterative corresponding point (ICP) algorithm is widely used to solve this problem. Unfortunately, the ICP algorithm has few guarantees in accuracy or in runtime.

In this talk I will deal with two aspects of this problem. First, I will show how to extend the ICP algorithm to handle outliers. I will argue that this is the correct way to handle outliers and that our approach preserves what nice properties that ICP has in practice. Second, I will give a polynomial algorithm to find a perfect bipartite matching under rigid motions which is guaranteed to give an epsilon approximation to the optimal matching under the RMS Distance. This is the first algorithm to give a guaranteed approximation to this problem under rigid motions.

This is from joint work with Carlo Tomasi and Ran Liu and joint work with Pankaj Agarwal.