Computing Diameter in the Streaming and (2008)
Sliding-window Models, Joan Feigenbaum, Sampath Kannan, Jian Zhang
Abstract 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...