Robust shape fitting via peeling and grating coresets

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

Research output: Contribution to journalArticlepeer-review

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/ε (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
Volume39
Issue number1-3
DOIs
StatePublished - Mar 2008

Keywords

  • Coresets
  • Geometric approximation algorithms
  • Shape fitting

ASJC Scopus subject areas

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

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

Cite this