## 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