Smoothed analysis of the ICP algorithm for arbitrary probability distributions

The Iterative Closest Point (ICP) algorithm is a commonly used algorithm to align two point clouds. Worst-case analysis gives an exponential upper bound on the running time, but the algorithm is observed to work more efficiently in practice. To reconcile this gap, Arthur and Vassilvitskii perform a smoothed analysis of the ICP by perturbing the inputs according to a Gaussian distribution. Their polynomial smoothed complexity implies that the ICP algorithm should perform well in practice. This paper generalizes their findings, by proving a polynomial smoothed complexity for two more general perturbation models. In both models, the points are drawn according to arbitrary probability density functions upper bounded by a perturbation parameter. In the first model, the functions’ support is bounded to the unit hypercube. In the second model, their support is unbounded, but the probability distribution has exponentially decreasing tails.