Robust Shape Fitting via Peeling and Grating Coresets

Written with Pankaj Agarwal and Sariel Har-Peled.

Discrete & Computational Geometry (DCG anniversary special issue), 39:38-58, 2008.

Also in Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 182-191, 2006.

Downloads: PDF, PS

Abstract: Let P be a set of n points in R^d. We show that a (k,ε)-kernel of P of size O(k/ε^(d-1)/2) can be computed in O(n+k²/ε^d-1) time, where a (k,ε)-kernel is a subset of P that ε-approximates the directional width of P, for any direction, when k outliers can be ignored in that direction. A (k,ε)-kernel is instrumental in solving shape fitting problems with k outliers. The size of the new kernel improves over the previous known upper bound O(k/ε^d-1), and is tight in the worst case. We also present a simple incremental algorithm for (1+ε)-fitting various shapes through a set of points with at most k outliers. The algorithm works by repeatedly "grating" critical points into a working set, till the working set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear-time algorithm for shape fitting with outliers.