Math @ Duke

Publications [#235512] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Yu, H, Robust Shape Fitting via Peeling and Grating Coresets,
Discrete & Computational Geometry, vol. 39 no. 13
(March, 2008),
pp. 3858, ISSN 01795376 [doi]
(last updated on 2018/11/17)
Abstract: Let P be a set of n points in ℝ d. A subset S of P is called a (k,ε)kernel if for every direction, the directional width of S εapproximates that of P, when k "outliers" can be ignored in that direction. We show that a (k,ε)kernel of P of size O(k/ε (d1)/2) can be computed in time O(n+k 2/ε d1). The new algorithm works by repeatedly "peeling" away (0,ε)kernels from the point set. We also present a simple εapproximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and 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, nearlinear εapproximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems. © 2007 Springer Science+Business Media, LLC.


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

