Streaming Diameter of High-Dimensional Points

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10511943" target="_blank" >RIV/00216208:11320/25:10511943 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.58" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2025.58</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2025.58" target="_blank" >10.4230/LIPIcs.ESA.2025.58</a>

Result language

angličtina

Original language name

Streaming Diameter of High-Dimensional Points

Original language description

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 O(ε&lt;sup&gt;-&lt;/sup&gt;&lt;sup&gt;2&lt;/sup&gt; log(&lt;sup&gt;1&lt;/sup&gt;&lt;inf&gt;ε&lt;/inf&gt; )) points. This improves by a factor of ε&lt;sup&gt;-&lt;/sup&gt;&lt;sup&gt;1&lt;/sup&gt; the previous space bound of Agarwal and Sharathkumar (SODA 2010), while retaining the state-of-the-art approximation guarantees, such as &lt;sup&gt;SQUARE ROOT&lt;/sup&gt;2 + ε for Diameter or Farthest Neighbor queries, and also offering a simpler and more complete argument. Moreover, we show that storing Ω(ε&lt;sup&gt;-&lt;/sup&gt;&lt;sup&gt;1&lt;/sup&gt;) points is necessary for a streaming (&lt;sup&gt;SQUARE ROOT&lt;/sup&gt;2 + ε)-approximation of Farthest Pair and Farthest Neighbor queries.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics Lipics

ISBN

978-3-95977-395-9

ISSN

1868-8969

e-ISSN

—

Number of pages

10

Pages from-to

58.1-58.10

Publisher name

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl, Německo

Event location

Varšava, Polsko

Event date

Sep 15, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—