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 R^{d}. We
show that a (k,µ)-kernel of P of size
O(k/µ^{(d-1)/2}) can be computed in time
O(n+k^{2}/µ^{d-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.