Dynamic coresets
Timothy M. Chan · 2008
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.