Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
From MaRDI portal
Publication:3558022
DOI10.1137/070683921zbMATH Open1202.68496OpenAlexW2034380011MaRDI QIDQ3558022FDOQ3558022
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
Recommendations
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Surface estimation for multiple misaligned point sets
- 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
Uses Software
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)
