Practical methods for shape fitting and kinetic data structures using core sets

ABSTRACT

The notion of ε-kernel was introduced by Agarwal et al. to set up a unified framework for computing various extent measures of a point set p approximately. Roughly speaking, a subset Q ⊆ P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of an ε-kernel by showing that it yields approximation algorithms for a wide range of problems.We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ³. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points.

REFERENCES

• 1: 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.
• 2: P. K. Agarwal, B. Aronov, and M. Sharir, Line transversals of balls and smallest enclosing cylinders in three dimensions, Discrete Comput. Geom., 21 (1999), 373--388.
• 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: 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]
• 6: P. K. Agarwal and J. Matoušek, On range searching with semialgebraic sets, Discrete Comput. Geom., 11 (1994), 393--418.
• 7: Pankaj K. Agarwal , Cecilia Magdalena Procopiuc , Kasturi R. Varadarajan, Approximation Algorithms for k-Line Center, Proceedings of the 10th Annual European Symposium on Algorithms, p.54-63, September 17-21, 2002
• 8: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
• 9: 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]
• 10: 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]
• 11: Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 13: T. M. Chan, Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus, Internat. J. Comput. Geom. Appl., 12 (2002), 67--85.
• 14: T. M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, this proceedings.
• 15: Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM (JACM), v.42 n.2, p.488-499, March 1995 [doi>10.1145/201019.201036]
• 16: Bernd Gartner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, v.24 n.5, p.1018-1035, Oct. 1995 [doi>10.1137/S0097539793250287]
• 17: B. Gärtner, Smallest enclosing ball --- fast and robust in C++, http://www.inf.ethz.ch/personal/gaertner/miniball.html
• 18: Sariel Har-Peled , Yusu Wang, Shape fitting with outliers, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777798]
• 19: P. Kumar, J. Mitchell, and E. Yildirim, Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions, Proc. 5th Workshop Algorithm Eng. Exper., 2003, pp. 45--55.
• 20: P. Kumar and E. Yildirim, Approximating minimum volume enclosing ellipsoids using core sets, Unpublished manuscript, 2003.
• 21: Large geometric models archive, http://www.cc.gatech.edu/projects/large_models/
• 22: D. Mount and S. Arya, ANN: library for approximate nearest neighbor searching, http://www.cs.umd.edu/~mount/ANN/
• 23: A. C. Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Comput., 11 (1982), 721--736.
• 24: Yunhong Zhou , Subhash Suri, Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions, SIAM Journal on Computing, v.31 n.5, p.1339-1357, 2002 [doi>10.1137/S0097539799363992]

INDEX TERMS

Primary 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

General Terms:
Algorithms, Experimentation

Keywords:
core sets, extent measures, kinetic data structures, shape fitting