## Abstract

Let P be a set of n points in ℝ^{d}. 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}), where a (k, ε)-kernel is a subset of P that ε-approximates the directional width of P, for any direction, when k outliers can be ignored in that direction. A (k, ε)-kernel is instrumental in solving shape fitting problems with k outliers, like computing the minimum-width annulus covering all but k of the input points. The size of the new kernel improves over the previous known upper bound O(k/ε^{d-1}) [17], and is tight in the worst case. The new algorithm works by repeatedly "peeling" away (0, ε)-kernels. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We also present a simple incremental algorithm for (1 + ε)-fitting various shapes through a set of points with at most k outliers. The algorithm 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-time algorithm for shape fitting with outliers. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing circle and minimum-width annulus.

Original language | English (US) |
---|---|

Pages | 182-191 |

Number of pages | 10 |

DOIs | |

State | Published - 2006 |

Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |

### Other

Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Miami, FL |

Period | 1/22/06 → 1/24/06 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)