article · 2002

Computing Diameter in the Streaming and Sliding-Window Models¤

Joan Feigenbaumy, Sampath Kannan Z, Jian Zhang X

Cited by 0Abstract and details only

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 -approximation1algorithm 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 windows model using O ( 1 3=2 log3 n(log R + log log n + log 1

Cite this paper

APA 7

Feigenbaumy, J., Z, S. K., & X, J. Z. (2002). Computing Diameter in the Streaming and Sliding-Window Models¤.

MLA 9

Feigenbaumy, Joan, et al. “Computing Diameter in the Streaming and Sliding-Window Models¤.” 2002.

Chicago

Feigenbaumy, Joan, Sampath Kannan Z, and Jian Zhang X. 2002. “Computing Diameter in the Streaming and Sliding-Window Models¤.”

Harvard

Feigenbaumy, J., Z, S.K. and X, J.Z. (2002) ‘Computing Diameter in the Streaming and Sliding-Window Models¤’.

BibTeX

@article{feigenbaumy2002computing,
  title = {{Computing Diameter in the Streaming and Sliding-Window Models¤}},
  author = {Feigenbaumy, Joan and Z, Sampath Kannan and X, Jian Zhang},
  year = {2002}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.