Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method

DOI10.1137/070683921zbMath1202.68496OpenAlexW2034380011MaRDI QIDQ3558022

Sergei Vassilvitskii, David Arthur

Publication date: 29 April 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070683921

zbMATH Keywords

ICP\(k\)-meanssmoothed analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ The planar \(k\)-means problem is NP-hard ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Nonrigid registration using Gaussian processes and local likelihood estimation ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ The Planar k-Means Problem is NP-Hard ⋮ Unnamed Item ⋮ Smoothed analysis of probabilistic roadmaps ⋮ Surface estimation for multiple misaligned point sets

Uses Software

• k-means++