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 (n) bits of space. We present a simple ε-approximation 4 algorithm for computing the diameter in the streaming model. Our main result is an ε-approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using O((1/ε 3/2 ) log 3 n(log R + log log n + log(1/ε))) 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. Key Words. Massive data streams, Sliding window, Diameter. In recent years, massive data sets have become increasingly important in a wide range of applications. In many of these applications the input can be viewed as a data stream [3] , [19], [9] that the algorithm reads in one pass. The algorithm should take little time to process each data element and should use little space in comparison with the input size. In some scenarios the input stream may be infinite, and the application may only care about recent data. In this case the sliding-window model [8] may be more appropriate. As in the streaming model, a sliding-window algorithm should go through the input stream once, and there is not enough storage space for all the data, even for the data in one window. In this paper we investigate the two-dimensional diameter problem in these two models. Given a set of points P, the diameter is the maximum, over all pairs x, y in P, of the distance between x and y. There are efficient algorithms to compute the exact diameter [6], [25] [5] . However, little has been done for computational-geometry problems in the streaming or sliding-window models. In particular, little is known about the diameter problem in these two models.
Feigenbaum, Kannan and Zhang REF gave an O(1/ǫ) space algorithm for computing the diameter of points in two dimensions in the streaming model and a O(
Computing Diameter in the Streaming and Sliding-Window Models
Algorithmica
Algorithmica
Mathematics Computer Science