×

Geometric optimization problems over sliding windows. (English) Zbl 1090.65068

Summary: The authors study the problem of maintaining an \((1 + \epsilon)\)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, they give a simple algorithm that only needs to store \(O(\frac{1}{\epsilon})\) 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. Then they extend the one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, the authors 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.

MSC:

65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1145/1008731.1008736 · Zbl 1204.68240 · doi:10.1145/1008731.1008736
[2] DOI: 10.1016/0925-7721(92)90001-9 · Zbl 0769.68037 · doi:10.1016/0925-7721(92)90001-9
[3] DOI: 10.1007/BF02712871 · Zbl 0857.68109 · doi:10.1007/BF02712871
[4] DOI: 10.1006/jagm.2000.1127 · Zbl 0969.68166 · doi:10.1006/jagm.2000.1127
[5] DOI: 10.1016/0196-6774(80)90015-2 · Zbl 0461.68065 · doi:10.1016/0196-6774(80)90015-2
[6] DOI: 10.1142/S0218195902000748 · Zbl 1152.68659 · doi:10.1142/S0218195902000748
[7] DOI: 10.1007/BF02187740 · Zbl 0681.68060 · doi:10.1007/BF02187740
[8] DOI: 10.1007/s00453-004-1105-2 · Zbl 1082.68020 · doi:10.1007/s00453-004-1105-2
[9] DOI: 10.1007/978-1-4612-1098-6 · doi:10.1007/978-1-4612-1098-6
[10] DOI: 10.1007/s00454-001-0029-8 · Zbl 0992.68229 · doi:10.1007/s00454-001-0029-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.