Dynamic coresets

Research output: Contribution to journalArticlepeer-review

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 per update 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 time O(log n) (or O(log log U) if the spread is bounded by U) 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.

Original languageEnglish (US)
Pages (from-to)469-488
Number of pages20
JournalDiscrete and Computational Geometry
Volume42
Issue number3
DOIs
StatePublished - 2009
Externally publishedYes

Keywords

  • Approximation algorithms
  • Dynamic data structures
  • Geometric optimization
  • Randomization
  • Width
  • Word RAM
  • k-Center

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

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

Cite this