No Access

GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS

TIMOTHY M. CHAN

School of Computer Science, University of Waterloo, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

Search for more papers by this author

and

BASHIR S. SADJAD

School of Computer Science, University of Waterloo, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

Search for more papers by this author

https://doi.org/10.1142/S0218195906001975Cited by:6 (Source: Crossref)

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

Work done by the first author was supported by an NSERC Research Grant and a Premiere's Research Excellence Award. A preliminary version of this work has appeared in Proc. 15th Int. Sympos. Algorithms and Computation (2004) and has also appeared as part of the second author's Master's thesis.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

P. K. Agarwal, S. Har-Peled and R. Varadarajan, J. ACM 51, 606 (2004). Crossref, Web of Science, Google Scholar
P. K. Agarwal, J. Matoušek and S. Suri, Comput. Geom.: Th. Appl. 1, 189 (1991). Crossref, Google Scholar
P. K. Agarwal and M. Sharir, Discr. Comput. Geom. 16, 317 (1996). Crossref, Web of Science, Google Scholar
S. Barequet and S. Har-Peled, J. Algorith. 38, 91 (2001). Crossref, Web of Science, Google Scholar
J. L. Bentley and J. B. Saxe, J. Algorith. 1, 301 (1980). Crossref, Google Scholar
T. M. Chan, Int. J. Comput. Geom. Appl. 12, 67 (2002). Link, Web of Science, Google Scholar
T. M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proc. 20th Ann. Symp. Computational Geometry (2004) pp. 152–159. Google Scholar
K. L. Clarkson and P. W. Shor, Discr. Comput. Geom. 4, 387 (1989). Crossref, Web of Science, Google Scholar
C. A. Duncan, M. T. Goodrich and E. A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proc. Eighth Ann. ACM-SIAM Symp. Discrete Algorithms (1997) pp. 121–130. Google Scholar
J. Feigenbaum, S. Kannan and J. Zhang, Algorithmica 41, 25 (2004). Crossref, Web of Science, Google Scholar
A. Goel, P. Indyk and K. Varadarajan, Reductions among high dimensional proximity problems, Proc. Twelfth Ann. ACM-SIAM Symp. Discrete Algorithms (2001) pp. 769–778. Google Scholar
M. Henzinger, P. Raghavan and S. Rajagopalan, Computing on data streams, Technical Report SRC-TN-1998-011, Hewlett Packard Laboratories (1998). . Google Scholar
J. Hershberger and S. Suri, Convex hulls and related problems in data streams, Proc. ACM SIGMOD/PODS Workshop on Management and Processing of Data Streams (2003) pp. 148–168. Google Scholar
P. Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proc. Fourteenth Ann. ACM-SIAM Symp. Discrete Algorithms (2003) pp. 539–545. Google Scholar
P. Indyk, Streaming algorithms for geometric problems, Proc. 16th Canadian Conf. Computational Geometry (2004) pp. 174–175. Google Scholar
S. M. Muthukrishnan, Data streams: Algorithms and applications, http://athos.rutgers.edu/~muthu/stream-1-1.ps (2003) . Google Scholar
F. P. Preparata and M. I. Shamos , Computational Geometry: An Introduction ( Springer-Verlag , 1985 ) . Crossref, Google Scholar
E. A. Ramos, Discr. Comput. Geom. 26, 233 (2001). Crossref, Web of Science, Google Scholar