Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235512] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Har-Peled, S; Yu, H, Robust Shape Fitting via Peeling and Grating Coresets, Discrete & Computational Geometry, vol. 39 no. 1-3 (March, 2008), pp. 38-58, ISSN 0179-5376 [doi]
    (last updated on 2018/11/17)

    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/ε (d-1)/2) can be computed in time O(n+k 2/ε d-1). 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, near-linear ε-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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320