Robust shape fitting via peeling and grating coresets

Let P be a set of n points in R-d supercript stop. A subset S of P is called a (k,epsilon)-kernel if for every direction, the directional width of S epsilon-approximates that of P, when k "outliers" can be ignored in that direction. We show that a (k,epsilon)-kernel of P of size O(k/epsilon((d-1)/2)) can be computed in time O(n+k(2)/epsilon(d-1)). The new algorithm works by repeatedly "peeling" away (0,epsilon)-kernels from the point set. We also present a simple epsilon-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and 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 epsilon-approximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems.