Robust shape fitting via peeling and grating coresets

Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu

Research output: Contribution to journalArticlepeer-review


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 2d-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.

Original languageEnglish (US)
Pages (from-to)38-58
Number of pages21
JournalDiscrete and Computational Geometry
Issue number1-3
StatePublished - Mar 2008


  • Coresets
  • Geometric approximation algorithms
  • Shape fitting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Robust shape fitting via peeling and grating coresets'. Together they form a unique fingerprint.

Cite this