TY - GEN

T1 - Dynamic coresets

AU - Chan, Timothy M.

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Dynamic data structures

KW - Geometric optimization

KW - Randomization

KW - Word RAM

UR - http://www.scopus.com/inward/record.url?scp=57349087665&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349087665&partnerID=8YFLogxK

U2 - 10.1145/1377676.1377680

DO - 10.1145/1377676.1377680

M3 - Conference contribution

AN - SCOPUS:57349087665

SN - 9781605580715

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 1

EP - 9

BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08

T2 - 24th Annual Symposium on Computational Geometry, SCG'08

Y2 - 9 June 2008 through 11 June 2008

ER -