Dynamic coresets

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give a dynamic data structure that can maintain an e-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 0(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 fc-centers in 0(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(l) randomized amortized time on the word RAM.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages1-9
Number of pages9
DOIs
StatePublished - Dec 12 2008
Externally publishedYes
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

Keywords

  • Approximation algorithms
  • Dynamic data structures
  • Geometric optimization
  • Randomization
  • Word RAM

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Dynamic coresets'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M. (2008). Dynamic coresets. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 1-9). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1377676.1377680