Robust shape fitting via peeling and grating coresets

ABSTRACT

Let P be a set of n points in R^d. We show that a (k, ε)-kernel of P of size O(k/ε^(d-1)/2) can be computed in time O(n + k²/ε^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.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paulo G. Franciosa , Jeffrey Scott Vitter, Efficient searching with linear constraints, Journal of Computer and System Sciences, v.61 n.2, p.194-216, Oct. 2000 [doi>10.1006/jcss.2000.1709]
• 2: P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir, Approximation and exact algorithms for minimum-width annuli and shells, Discrete Comput. Geom., 24 (2000), 687--705.
• 3: P. K. Agarwal, B. Aronov, and M. Sharir, Exact and approximation algorithms for minimum-width cylindrical shells, Discrete Comput. Geom., 26 (2001), 307--320.
• 4: P. K. Agarwal, L. J. Guibas, J. Hershberger, and E. Veach, Maintaining the extent of a moving point set, Discrete Comput. Geom., 26 (2001), 353--374.
• 5: P. K. Agarwal, S. Har-Peled, and K. Varadarajan, Geometric approximation via coresets, in: Combinatorial and Computational Geometry (J. E. Goodman, J. Pach, and E. Welzl, eds.), Math. Sci. Research Inst. Pub., Cambridge, 2005.
• 6: Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004 [doi>10.1145/1008731.1008736]
• 7: Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Journal of Algorithms, v.38 n.1, p.91-109, Jan. 2001 [doi>10.1006/jagm.2000.1127]
• 9: Julien Basch , Leonidas J. Guibas, Data structures for mobile data, Journal of Algorithms, v.31 n.1, p.1-28, April 1999 [doi>10.1006/jagm.1998.0988]
• 10: T. M. Chan, Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus, Internat. J. Comput. Geom. Appl., 12 (2002), 67--85.
• 11: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.570, November 16-19, 2002
• 12: Timothy M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997843]
• 13: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 14: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 15: B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
• 16: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 17: Sariel Har-Peled , Yusu Wang, Shape Fitting with Outliers, SIAM Journal on Computing, v.33 n.2, p.269-285, 2004 [doi>10.1137/S0097539703427963]
• 18: Large geometric models archive. Georgia Tech. http://www.cc.gatech.edu/projects/large_models/.
• 19: Jiří Matoušek, Approximate levels in line arrangements, SIAM Journal on Computing, v.20 n.2, p.222-227, April 1990 [doi>10.1137/0220013]
• 20: J. Matoušek, On geometric optimization with few violated constraints, Discrete Comput. Geom., 14 (1995), 365--384.
• 21: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 22: Hai Yu , Pankaj K. Agarwal , Raghunath Poreddy , Kasturi R. Varadarajan, Practical methods for shape fitting and kinetic data structures using core sets, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997858]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

General Terms:
Algorithms, Theory