
arXiv: 2505.16720
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}(\varepsilon^{-2}\log(\frac{1}{\varepsilon}))$ points. This improves by a factor of $\varepsilon^{-1}$ the previous space bound of Agarwal and Sharathkumar (SODA 2010), while offering a simpler and more complete argument. We also show that storing $Ω(\varepsilon^{-1})$ points is necessary for a $(\sqrt{2}+\varepsilon)$-approximation of Farthest Pair or Farthest Neighbor queries.
FOS: Computer and information sciences, coreset, streaming algorithm, Computer Science - Data Structures and Algorithms, minimum enclosing ball, Data Structures and Algorithms (cs.DS), diameter, farthest pair, ddc: ddc:004
FOS: Computer and information sciences, coreset, streaming algorithm, Computer Science - Data Structures and Algorithms, minimum enclosing ball, Data Structures and Algorithms (cs.DS), diameter, farthest pair, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
