Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method

DOI10.1137/070683921MaRDI QIDQ3558022zbMATH OpenOpenAlexFDO

Authors David Arthur, Sergei Vassilvitskii

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

\(k\)-meanssmoothed analysisICP

Mathematics Subject Classification ID

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

Recommendations

• On the performance of the ICP algorithm
• \(k\)-means requires exponentially many iterations even in the plane
• Smoothed analysis of the \(k\)-means method
• Improved smoothed analysis of the \(k\)-means method
• How fast is the \(k\)-means method?

Cited in

(15)

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

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558022)