Dynamic coresets

ABSTRACT

We give a dynamic data structure that can maintain an μ-coreset of n points, with respect to the extent measure, in O(log n) time for any constant μ > 0 and any constant dimension. The previous method by Agarwal, Har-Peled, and Varadarajan requires polylogarithmic update time. For points with integer coordinates bounded by U, we alternatively get O(log log U) time. Numerous applications follow, for example, on dynamically approximating the width, smallest enclosing cylinder, minimum bounding box, or minimum-width annulus. We can also use the same approach to maintain approximate k-centers in O(min log n, log log U) randomized amortized time for any constant k and any constant dimension.

For the smallest enclosing cylinder problem, we also show that a constant-factor approximation can be maintained in O(1) randomized amortized time on the word RAM.

REFERENCES

• 1: P.K. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom. 21:373--388, 1999.
• 2: 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]
• 3: P.K. Agarwal, S. Har-Peled, and K.R. Varadarajan. Geometric approximation via coresets. In Current Trends in Combinatorial and Computational Geometry (E. Welzl, ed.), Cambridge University Press, New York, to appear.
• 4: Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Robust shape fitting via peeling and grating coresets, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.182-191, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109579]
• 5: P.K. Agarwaland J. Matoušek. Dynamic half-space range reporting and its applications. Algorithmica 13:325--345, 1995.
• 6: Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003 [doi>10.1016/S0196-6774(02)00295-X]
• 7: Pankaj K. Agarwal , Micha Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications, v.1 n.2, p.65-78, Sept. 1991 [doi>10.1016/S0925-7721(00)00026-2]
• 8: P.K. Agarwal and M. Sharir. Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom. 16:317--337, 1996.
• 9: Pankaj K. Agarwal , Hai Yu, A space-optimal data-stream algorithm for coresets in the plane, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247071]
• 10: M. Badoiu and K.L. Clarkson. Optimal core-sets for balls. Manuscript, 2003. Preliminary version in Proc. 14th ACM-SIAM Sympos. Discrete Algorithms pages 801--802, 2003.
• 11: 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]
• 12: 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]
• 13: J. Bentley and J. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1:301--358, 1980.
• 14: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.617-626, November 16-19, 2002
• 15: Timothy M. Chan, Dynamic planar convex hull operations in near-logarithmic amortized time, Journal of the ACM (JACM), v.48 n.1, p.1-12, Jan. 2001 [doi>10.1145/363647.363652]
• 16: T.M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl. 12:67--85, 2002.
• 17: T.M. Chan. A fully dynamic algorithm for planar width. Discrete Comput. Geom. 30:17--24, 2003.
• 18: Timothy M. Chan, Semi-Online Maintenance of Geometric Optima and Measures, SIAM Journal on Computing, v.32 n.3, p.700-716, 2003 [doi>10.1137/S0097539702404389]
• 19: Timothy M. Chan, A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1196-1202, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109689]
• 20: Timothy M. Chan, Faster core-set constructions and data-stream algorithms in fixed dimensions, Computational Geometry: Theory and Applications, v.35 n.1, p.20-35, August 2006 [doi>10.1016/j.comgeo.2005.10.002]
• 21: Timothy M. Chan, Well-separated pair decomposition in linear time?, Information Processing Letters, v.107 n.5, p.138-141, August, 2008 [doi>10.1016/j.ipl.2008.02.008]
• 22: T.M. Chan and M. Patraşcu. Point location in sublogarithmic time and other transdichotomous results in computational geometry. Submitted to SIAM J. Comput. Preliminary versions in Proc. 47th IEEE Sympos. Found. Comput. Sci. pages 325--332 and 333--342, 2006.
• 23: Timothy M. Chan , Mihai Pǎtraşcu, Voronoi diagrams in n · 2^{o(√lg lg n)} time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250796]
• 24: T.M. Chan and B.S. Sadjad. Geometric optimization problems over sliding windows. Int. J. Comput. Geom. Appl. 16:145--157, 2006.
• 25: B. Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory IT-31:509--517, 1985.
• 26: K.L. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng. Approximating center points with iterative Radon points. Int. J. Comput. Geom. Appl. 6:357--377, 1996.
• 27: Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
• 28: M. Edwards and K.R. Varadarajan. No coreset, no cry:II. In Proc. 25th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci. Lect. Notes Comput. Sci., vol. 3821, Springer-Verlag, pages 107--115, 2005.
• 29: J. Feigenbaum, S. Kannan, and J. Zhang. Computing diameter in the streaming and sliding-window models. Algorithmica 41:25--41, 2004.
• 30: Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064116]
• 31: Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060622]
• 32: T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38:293--306, 1985.
• 33: Sariel Har-Peled, Clustering Motion, Discrete & Computational Geometry, v.31 n.4, p.545-565, March 2004 [doi>10.1007/s00454-004-2822-7]
• 34: S. Har-Peled. No coreset, no cry. In Proc. 24th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci. Lect. Notes Comput. Sci., vol. 3328, Springer-Verlag, pages 324--335, 2004.
• 35: Sariel Har-Peled , Akash Kushal, Smaller Coresets for k-Median and k-Means Clustering, Discrete & Computational Geometry, v.37 n.1, p.3-19, January 2007 [doi>10.1007/s00454-006-1271-x]
• 36: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 37: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 38: 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]
• 39: Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007413]
• 40: R. Janardan. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl. 3:331--344, 1993.
• 41: J. Matoušek. Derandomization in computational geometry.In Handbook of Computational Geometry (J. Urrutia and J. Sack, ed.), North-Holland, pages 559--595, 2000.
• 42: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 43: M.H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Sys. Sci. 23:166--204, 1981.
• 44: G. Rote, C. Schwarz, and J. Snoeyink. Maintaining the approximate width of a set of points in the plane. In Proc. 5th Canad. Conf. Comput. Geom. pages 258--263, 1993.
• 45: Mikkel Thorup, Equivalence between Priority Queues and Sorting, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.125-134, November 16-19, 2002
• 46: P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inform. Process. Lett. 6:80--82, 1977.
• 47: 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]
• 48: H. Zarrabi-Zadeh. An almost space-optimal streaming algorithm for coresets in fixed dimensions. Manuscript, 2007.

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, Theory

Keywords:
approximation algorithms, dynamic data structures, geometric optimization, randomization, word ram