Robust shape fitting via peeling and grating coresets
Pankaj K. Agarwal, Sariel Har-Peled, Hai Bo Yu · Symposium on Discrete Algorithms · 2006
Let P be a set of n points in Rd. We show that a (k, e)-kernel of P of size O(k/e(d-1)/2) can be computed in time O(n + k2/ed-1), where a (k, e)-kernel is a subset of P that e-approximates the directional width of P, for any direction, when k outliers can be ignored in that direction. A (k, e)-kernel is instrumental in solving shape fitting problems with k outliers, like computing the minimum-width annulus covering all but k of the input points. The size of the new kernel improves over the previous known upper bound O(k/ed-1) [17], and is tight in the worst case. The new algorithm works by repeatedly peeling away (0, e)-kernels. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs.We also present a simple incremental algorithm for (1 + e)-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. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing circle and minimum-width annulus.