TY - JOUR

T1 - Robust shape fitting via peeling and grating coresets

AU - Agarwal, Pankaj K.

AU - Har-Peled, Sariel

AU - Yu, Hai

N1 - Funding Information:
A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P. is supported by a NSF CAREER award CCR-0132901.

PY - 2008/3

Y1 - 2008/3

N2 - 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.

AB - 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.

KW - Coresets

KW - Geometric approximation algorithms

KW - Shape fitting

UR - http://www.scopus.com/inward/record.url?scp=40349111114&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40349111114&partnerID=8YFLogxK

U2 - 10.1007/s00454-007-9013-2

DO - 10.1007/s00454-007-9013-2

M3 - Article

AN - SCOPUS:40349111114

VL - 39

SP - 38

EP - 58

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 1-3

ER -