Robust Shape Fitting via Peeling and Grating Coresets
Pankaj K. Agarwal,
Sariel Har-Peled,
and Hai Yu.
To appear in 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+k2/µ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.
Postscript,
PDF.
Last modified: Fri Oct 14 12:51:44 CDT 2005