Streaming Diameter of High-Dimensional Points
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909620272889856 |
|---|---|
| author | Halldórsson, Magnús M. Matsakis, Nicolaos Veselý, Pavel |
| author_facet | Halldórsson, Magnús M. Matsakis, Nicolaos Veselý, Pavel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Streaming Diameter of High-Dimensional Points Halldórsson, Magnús M. Matsakis, Nicolaos Veselý, Pavel Data Structures and Algorithms 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. |
| title | Streaming Diameter of High-Dimensional Points |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.16720 |