University of Twente Student Theses


Smoothed analysis of the ICP algorithm for arbitrary probability distributions

Schmit, C. (2020) Smoothed analysis of the ICP algorithm for arbitrary probability distributions.

[img] PDF
Abstract: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.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page