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 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.
Original language | English (US) |
---|---|
Pages (from-to) | 38-58 |
Number of pages | 21 |
Journal | Discrete and Computational Geometry |
Volume | 39 |
Issue number | 1-3 |
DOIs | |
State | Published - 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