Computing Diameter in the Streaming and Sliding-Window
Models |
| |
Authors: | Joan Feigenbaum Sampath Kannan Jian Zhang |
| |
Affiliation: | 1. Department of Computer Science, Yale University,
P.O. Box 208285, New Haven, CT 06520-8285, USA 2. Department of Computer
and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA
|
| |
Abstract: | We investigate the diameter
problem in the streaming and sliding-window
models. We show that, for
a stream of nn points or a sliding window of size nn, any exact
algorithm for diameter requires W(n)\Omega(n) bits of
space. We present a simple e\epsilon-approximation algorithm
for computing the diameter in the streaming model. Our main result
is an e\epsilon-approximation algorithm
that maintains the diameter in two dimensions in the sliding-window
model using O((1/e3/2) log3n(logR+loglogn + log(1/e)))O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n +
\log ({1}/{\epsilon}))) bits of space, where RR 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|