Computing Diameter in the Streaming and Sliding-Window Models (Preprint)
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 Omega(n) 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 [(1/epsilon (exp 3/2) log3 n(log R + log log n + log 1/epsilon ))] 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 23, 2002
- Accession Number
- ADA461989
Entities
People
- Jian Zhang
- Joan Feigenbaum
- Sampath Kannan
Organizations
- Yale University