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).