Full text  Click to download. 
Citation  Algorithmica 41 (2005), pp. 2541.

Authors  Joan Feigenbaum
Sampath Kannan Jian Zhang 
We investigate the diameter problem in the streaming and slidingwindow 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 \epsilonapproximation algorithm for computing the diameter in the streaming model. Our main result is an \epsilonapproximation algorithm that maintains the diameter in two dimensions in the slidingwindow model using O(1/\epsilon^{3/2} log^3n(log(R)+loglog(n)+log(1/\epsilon))) bits of space, where R is the maximum, over all windows, of the ratio of the diameter to the minimum nonzero distance between any two points in the window.