Home Bookmarks Papers Blog

Robust Shape Fitting via Peeling and Grating Coresets

Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu.

In DCG (08), and SODA 06.
Let P be a set of n points in Rd. We show that a (k,µ)-kernel of P of size O(k/µ(d-1)/2) can be computed in time O(n+k2d-1), 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, 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/µd-1) [hw04], and is tight in the worst case. The new algorithm works by repeatedly ``peeling'' away (0,µ)-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+µ)-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.

Last modified: Fri Oct 14 12:51:44 CDT 2005