Geometric optimization problems over sliding windows

Timothy M. Chan, Bashir S. Sadjad

Research output: Contribution to journalArticlepeer-review

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(1/ε 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.

Original languageEnglish (US)
Pages (from-to)145-157
Number of pages13
JournalInternational Journal of Computational Geometry and Applications
Volume16
Issue number2-3
DOIs
StatePublished - Jun 2006
Externally publishedYes

Keywords

  • Approximation algorithms
  • Data stream
  • Diameter
  • Sliding window
  • Width

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Geometric optimization problems over sliding windows'. Together they form a unique fingerprint.

Cite this