We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS.
- Authors
Chan, Timothy M.; Sadjad, Bashir S.
- Abstract
We study the problem of maintaining a (1 + ∊)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store $O({\frac{1}{\epsilon}}\,{\rm log}\,R)$ points at any time, where the parameter R denotes the "spread" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case.
- Subjects
WINDOWS; DIAMETER; APPROXIMATION theory; MATHEMATICAL optimization; LOGARITHMS; ALGORITHMS; DIMENSIONS
- Publication
International Journal of Computational Geometry & Applications, 2006, Vol 16, Issue 2/3, p145
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195906001975