Metraipolis › archive › dc_fbf4ee7ff6e0
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams — arXiv:2609.19089
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19089
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:11:23.819Z
- SHA-256 of the archived text
f4d58c5fd676cde9408c88183a812826a39e6ea9adc565b0d7afbd474afbb6a9- Stable URL of this page
https://metraipolis.com/documento/dc_fbf4ee7ff6e0
How to cite
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams — arXiv:2609.19089 — arXiv (en), https://arxiv.org/abs/2609.19089 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fbf4ee7ff6e0 (Metraipolis archive dc_fbf4ee7ff6e0, sha256 f4d58c5fd676cde9408c88183a812826a39e6ea9adc565b0d7afbd474afbb6a9)
BibTeX
@misc{dcfbf4ee7ff6e0,
title = {A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams — arXiv:2609.19089},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19089},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fbf4ee7ff6e0; sha256 f4d58c5fd676cde9408c88183a812826a39e6ea9adc565b0d7afbd474afbb6a9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19089. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matching lower bound. Any dynamic streaming algorithm which can $c$-approximate the diameter of $n$ Euclidean vectors must use $n^{\tilde{\Omega}(1/c^2)}$ space.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2609.19089 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.278Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).