Math @ Duke

Publications [#235481] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Yu, H, Robust shape fitting via peeling and grating coresets,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2006),
pp. 182191 [doi]
(last updated on 2017/12/16)
Abstract: Let P be a set of n points in ℝd. We show that a (k, ε)kernel of P of size O(k/ε(d1)/2) can be computed in time O(n + k2/εd1), 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 minimumwidth annulus covering all but k of the input points. The size of the new kernel improves over the previous known upper bound O(k/εd1) [17], 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, nearlineartime algorithm for shape fitting with outliers. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing circle and minimumwidth annulus.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

