Accession Number:

ADA461989

Title:

Computing Diameter in the Streaming and Sliding-Window Models (Preprint)

Descriptive Note:

Journal article

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Report Date:

2002-12-23

Pagination or Media Count:

15.0

Abstract:

We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires Omegan bits of space. We present a simple epsilon-approximation algorithm for computing the diameter in the streaming model. Our main result is an epsilon-approximation algorithm that maintains the diameter in two dimensions in the sliding windows model using Omicron 1epsilon exp 32 log3 nlog R log log n log 1epsilon bits of space, where R is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window.

Subject Categories:

  • Statistics and Probability
  • Operations Research
  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE