Streaming Diameter of High-Dimensional Points

Abstract

We improve the space bound for streaming approximation of Diameter but also of Farthest Neighbor queries, Minimum Enclosing Ball and its Coreset, in high-dimensional Euclidean spaces. In particular, our deterministic streaming algorithms store $\mathcal{O}({\epsilon }^{-2}\log (\frac{1}{\epsilon }))$ points. This improves by a factor of ${\epsilon }^{-1}$ the previous space bound of Agarwal and Sharathkumar (SODA 2010), while offering a simpler and more complete argument. We also show that storing $\hat{I}\text{c◯}({\epsilon }^{-1})$ points is necessary for a $(\sqrt{2}+\epsilon )$-approximation of Farthest Pair or Farthest Neighbor queries.