betaFeedback

WorksComputer Science

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

Abstract

We give faster algorithms for diameter and farthest-neighbor search in high-dimensional Euclidean space. For every fixed 1<c<21<c<\sqrt2, we maintain an actual factor-cc diameter pair under arbitrary point insertions and deletions, with worst-case update time n^{2/c^2-1}\poly(d,\log n) and space n^{2/c^2}\poly(d,\log n), suppressing logarithmic dependence on the execution length and failure probability. Here nn bounds the number of active points. The update exponent improves Indyk's algorithm~\cite{indyk} (SODA'03) bound from 1/c21/c^2 to 2/c2−12/c^2-1, while the space exponent improves from 1+1/c21+1/c^2 to 2/c22/c^2. At c=3/2c=\sqrt{3/2}, the update exponent decreases from 2/32/3 to 1/31/3. A separate construction achieves approximation exactly 2\sqrt2 with update time polynomial in dd and log⁡n\log n. All these guarantees hold against adaptive updates, even when every previous random choice is exposed. We also improve the time–space tradeoff near linear space. This construction has an always-correct variant with expected amortized update bounds and requires no advance bound on the number of updates. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation 2−ε\sqrt2-\varepsilon, the diameter time is n1+O(ε)n^{1+O(\varepsilon)}, and the query time is nO(ε)+o(1)n^{O(\varepsilon)+o(1)} with near-linear preprocessing and space, up to polynomial input-parameter factors. On binary points, this improves the nO(θ)n^{O(\sqrtθ)} overhead of the algorithm that Andoni, Jiang, and Zharkov~\cite{ajz2026} (STOC'26) for Hamming approximation 2−θ2-θ to nO(θ)+o(1)n^{O(θ)+o(1)}.

Introduction

High-dimensional data are often represented by vectors, and distances between these vectors measure how different two observations are. Finding a farthest point is a basic operation in diversity maximization, outlier detection, and iterative learning procedures [11]. The diameter summarizes the largest separation within the data and is closely related to enclosing balls and clustering [7, 10]. For example, consider a collection of feature vectors that changes as observations arrive or expire. A pair of well-separated current vectors describes the collection’s extent; a farthest-neighbor query asks for an observation most different from a specified vector.

Recomputing either answer by scanning the entire collection can be expensive when such operations are repeated.

For a finite point set P⊆RdP \subseteq\mathbb{R}^{d}, its Euclidean diameter is diam⁡(P)=max⁡x,y∈P∥x−y∥\operatorname{diam}(P) = \max_{x,y\in P} \lVert x-y\rVert. A factor-cc diameter pair is a pair x,y∈Px,y \in P with ∥x−y∥≥diam⁡(P)/c\lVert x-y\rVert\ge\operatorname{diam}(P)/c. For a query q∈Rdq \in\mathbb{R}^{d}, a factor-cc farthest neighbor is a point p∈Pp \in P with ∥q−p∥≥max⁡x∈P∥q−x∥/c\lVert q-p\rVert\ge\max_{x\in P}\lVert q-x\rVert/c; the query need not belong to PP. We study fully dynamic diameter, where individual points may be inserted or deleted, and also obtain a farthest-neighbor structure for a fixed point set. The dimension is an input parameter, and our bounds have polynomial dependence on dd.

Why deletions and adaptivity matter. An insertion can create a new farthest pair, while a deletion can remove an endpoint of the pair currently stored by the algorithm. After such a deletion, the structure must find a sufficiently long pair among the remaining points, even if it has never returned that pair before. Moreover, an application may choose its next update or query after seeing earlier answers. An oblivious adversary fixes the entire operation sequence in advance; an adaptive adversary may use the history of the computation. We allow the latter to see all previous random choices as well as all answers. Only the fresh randomness used after the next operation is fixed remains unknown. This is the robust dynamic model studied in [10]. It is also useful when a geometric data structure is called by another algorithm whose later requests depend on its earlier answers.

Previous dynamic and streaming bounds. Indyk’s asymmetric embedding [23]1 gives a fully dynamic factor-cc diameter approximation with O~(dn1/c2)\widetilde{O}(dn^{1/c^{2}}) amortized update time. Its projection lists use O~(dn+n1+1/c2)\widetilde{O}(dn+n^{1+1/c^{2}}) space. Here nn bounds the number of active points, and the tilde suppresses logarithmic factors. The guarantee does not provide the exposed-randomness robustness considered here.

A different line achieves an approximation slightly larger than 2\sqrt{2} with much faster updates. Agarwal and Sharathkumar’s blurred-ball method [7] is an insertion-only streaming algorithm: it gives a (2+ε)(\sqrt{2}+\varepsilon)-approximate diameter using O(dε−3log⁡(1/ε))O(d\varepsilon^{-3}\log(1/\varepsilon)) space and amortized update time. Chan and Pathak [15] extend the underlying enclosing-ball approach to fully dynamic updates. For fixed ε>0\varepsilon> 0, the resulting diameter structure has Oε(dlog⁡n)O_{\varepsilon}(d\log n) expected amortized update time against an oblivious adversary; the diameter consequence is stated explicitly in [10 Appendix A]. Thus insertion-only streaming and fully dynamic maintenance have different guarantees and should be distinguished.

Banihashem et al. [BCG+25] obtain a factor-2 approximation with worst-case poly⁡(d,log⁡t)\operatorname{poly}(d,\log t) update time over tt updates against an adaptive adversary that sees previous random choices. Their central idea is to use a centerpoint as a representative that remains useful after deletions.2 Their representative is taken in the original space. Our work is motivated by this connection between centerpoints and robust dynamic diameter. We add a squared-norm coordinate before choosing the representative, thereby retaining a variance term that is absent from the original-space argument.

These results leave a clear quantitative question. Above 2\sqrt{2}, known structures have update time almost linear in the dimension and logarithmic in the set size. Below 2\sqrt{2}, Indyk’s update bound has a positive power of nn that approaches 1/21/2 as cc approaches 2\sqrt{2}. We ask:

Can one maintain a cc-approximate diameter pair below 2\sqrt{2} with an update exponent that tends to zero at 2\sqrt{2}, while supporting arbitrary deletions and fully adaptive updates?

Our answer is affirmative. The same geometry also gives faster farthest-neighbor queries on a fixed data set, with one success event valid for every query vector.

Main results

We first state the dynamic diameter bounds. The capacity n≥2n \ge2 is an upper bound on ∣P∣|P| throughout the execution. For a Monte Carlo structure, t≥1t \ge1 is an upper bound on the number of updates and δ∈(0,1/2)\delta\in(0,1/2) is the allowed probability that any answer is incorrect. All guarantees below permit the adaptive adversary just defined. A diameter query returns the two stored point identifiers and a reference to their previously computed squared distance in O(1)O(1) time. Writing out coordinates or the exact squared distance takes time proportional to the output length.

The notation poly⁡c(d,L)\operatorname{poly}_c(d,L) denotes a polynomial in dd and LL whose degree and coefficients may depend on the fixed approximation factor cc. In particular, it contains no additional power of nn. The arithmetic model counts operations and comparisons on coordinates; § 3 also specifies implementations for rational coordinates and the polynomial dependence on their bit length.

The following is our main update bound.

Theorem 1.1 (Fully dynamic diameter below 2\sqrt{2}). For every fixed 1<c<21<c<\sqrt{2}, a fully dynamic structure maintains a factor-cc diameter pair with worst-case update time n2/c2−1poly⁡c(d,log⁡(2nt/δ))n^{2/c^2-1}\operatorname{poly}_c(d,\log(2nt/\delta)) and space n2/c2poly⁡c(d,log⁡(2nt/δ))n^{2/c^2}\operatorname{poly}_c(d,\log(2nt/\delta)). With probability at least 1−δ1-\delta, all answers during the first tt adaptive updates are correct.

Compared with Indyk’s exponents, both the update and space exponents decrease by $1-1/c^2$ throughout 1<c<21<c<\sqrt{2}. At c=3/2c=\sqrt{3}/2, the update exponent decreases from 2/32/3 to 1/31/3, and the space exponent from 5/35/3 to $4/3. As cc increases to 2\sqrt{2}, our update exponent tends to zero and the space exponent tends to one. Figure 1 shows this comparison. The theorem also gives worst-case updates and robustness to exposed previous randomness.

Update exponents as a function of the approximation factor

Figure 1. Update exponents as a function of the approximation factor. The red curve improves both exponents of Indyk’s dynamic diameter bound. The green curve uses less space and is the limiting exponent of our always-correct construction; its time has an additional vanishing o(1)o(1) term. The three curves have the distinct space bounds shown in the legend.

The endpoint requires a separate argument: the angular search used below 2\sqrt{2} is unnecessary there. To state an explicit polynomial bound, put D=d+3D=d+3 and H=⌈log⁡2(2Dnt/δ)⌉H=\lceil\log_2(2Dnt/\delta)\rceil.

Theorem 1.2 (The exact 2\sqrt{2} endpoint). A fully dynamic structure maintains a factor-2\sqrt{2} diameter pair with worst-case update time O(D19H18)O(D^{19}H^{18}) and space O(nD19H18)O(nD^{19}H^{18}). With probability at least 1−δ1-\delta, every answer during the first tt adaptive updates is correct. For rational coordinates of at most BB bits, an always-correct variant uses npoly⁡(d,B,log⁡(2n))n\operatorname{poly}(d,B,\log(2n)) space and poly⁡(d,B,log⁡(2n))\operatorname{poly}(d,B,\log(2n)) expected amortized update time, without a prescribed bound on the number of updates.

The displayed polynomial is one explicit bound for the construction; its degrees are not optimized. Lemma 7.2 derives it by substituting the centerpoint construction time and the exact-leaf cutoff into the replacement schedule. The significance of the endpoint is its polylogarithmic dependence on nn at approximation exactly 2\sqrt{2}.

Time–space tradeoffs. The main theorem balances the update exponent and the extra exponent above linear space. More generally, let σ\sigma specify the space bound n1+σn^{1+\sigma}, apart from polynomial factors. Write g=c2−1g=c^2-1 and ρ=2/c2−1\rho=2/c^2-1. For 0≤σ≤ρ0\le\sigma\le\rho, storing the filter lists explicitly gives update exponent

Qc(σ)=(1−g2−gσ)2.Q_c(\sigma)=\left(\sqrt{1-g^2}-g\sqrt{\sigma}\right)^2.

Thus Theorem 1.1 extends to the bounds

update timenQc(σ)poly⁡c,σ(d,log⁡(2nt/δ)),spacen1+σpoly⁡c,σ(d,log⁡(2nt/δ)).\begin{aligned} \text{update time}\quad&n^{Q_c(\sigma)}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)),\\ \text{space}\quad&n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)). \end{aligned}

At σ=ρ\sigma=\rho both exponents beyond the leading linear space factor equal ρ\rho; at σ=0\sigma=0 the update exponent is Qc(0)=c2(2−c2)Q_c(0)=c^2(2-c^2). These bounds have no no(1)n^{o(1)} overhead.

Our second construction improves the update exponent when the space is close to linear. It represents point–filter incidences implicitly and recovers only those needed by a search. The quantities below describe its curve: χc\chi_c is the exponent at linear space, and ucu_c is the point where the improved linear branch meets QcQ_c. Set

χc=2−1+3g2,uc=g2(1−g2)(1+g2+1+3g2)2.\chi_c=2-\sqrt{1+3g^2},\qquad u_c=\frac{g^2(1-g^2)}{(1+g^2+\sqrt{1+3g^2})^2}.

and

Λc(σ)={χc−(3−χc)σ,0≤σ≤uc,Qc(σ),uc≤σ≤ρ.\Lambda_c(\sigma)= \begin{cases} \chi_c-(3-\chi_c)\sigma, & 0\leq\sigma\leq u_c,\\ Q_c(\sigma), & u_c\leq\sigma\leq\rho. \end{cases}

The first branch is tangent to QcQ_c at ucu_c, and is strictly below it for 0≤σ<uc0\leq\sigma<u_c. This improvement comes with a vanishing additive term in the time exponent. It also admits an always-correct (Las Vegas) implementation: randomness affects the work, but never the validity of an answer.

See also Figure 2 for the two curves at a fixed approximation factor.

Time–space tradeoff at $c=\sqrt{9/5}$

Figure 2. The time–space tradeoff at c=9/5c=\sqrt{9/5}. Space is n1+σn^{1+\sigma} up to polynomial factors. The implicit construction replaces the initial part of the explicit curve by its tangent at uc≈0.0205u_c\approx0.0205, improving the update exponent near linear space. Its running time has an additional vanishing o(1)o(1) term; the space exponent stays 1+σ1+\sigma.

Theorem 1.3 (Improved tradeoff with zero error). For fixed $1<c<\sqrt{2}$ and 0≤σ≤ρ0\leq\sigma\leq\rho, rational points with coordinate bit length at most BB admit an always-correct fully dynamic factor-cc diameter structure with space n1+σpoly⁡c,σ(d,B,log⁡(2n))n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)) and expected amortized update time nΛc(σ)+o(1)poly⁡c,σ(d,B,log⁡(2n))n^{\Lambda_c(\sigma)+o(1)}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)). It supports adaptive update sequences of arbitrary length. For a prescribed tt and δ\delta, a Monte Carlo variant has the same exponents, worst-case update time, and polynomial logarithmic dependence on $t/\delta.

Expected amortized time bounds the expected total work over every fixed finite prefix of an adaptive execution starting from the empty set. It includes construction, unsuccessful attempts, and rebuilding. The space bound includes all simultaneously live structures and their workspace. The following quantitative version makes the o(1)o(1) term in Theorem 1.3 explicit.

Corollary 1.4 (Explicit vanishing overhead). The o(1)o(1) in Theorem 1.3 can be replaced by Cc,σ(log⁡(2n))−1/100C_{c,\sigma}(\log(2n))^{-1/100} for one algorithm and a constant Cc,σC_{c,\sigma} depending only on c,σc,\sigma. The polynomial degrees in dd, BB, log⁡(2n)\log(2n) are fixed, and the space exponent remains 1+σ1+\sigma.

The proof is Theorem D.1 in Appendix § 14. In particular, increasing the dimension does not change the displayed exponent of nn. At linear space, that exponent tends to χc\chi_c; for c=1+εc=1+\varepsilon it equals 1−6ε2+O(ε3)1-6\varepsilon^2+O(\varepsilon^3). The accuracy is fixed in these statements: the constants need not be polynomial in 1/ε1/\varepsilon.

Static diameter and arbitrary farthest-neighbor queries. Inserting all input points immediately gives static diameter algorithms. The geometric reduction also supports arbitrary queries to a fixed data set. These are separate consequences: the fully dynamic theorems maintain one pair, while the static query structure returns a farthest neighbor of any supplied q∈Rdq\in\mathbb{R}^d.

References

  1. [1]Boris Aronov, Jean Cardinal, Justin Dallant, and John Iacono. A general technique for searching in implicit sets via function inversion. In 2024 Symposium on Simplicity in Algorithms (SOSA), pages 215–223, 2024. Full version revised April 22, 2026; journal version in Algorithmica.
  2. [2]Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2016.arxiv.org/abs/1608.04355
  3. [3]Josh Alman, Timothy M. Chan, and Ryan Williams. Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 637–649, 2020.
  4. [4]Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov. Approximate orthogonal vectors and diameter via regularity lemma. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 1477–1488, 2026.DOI
  5. [5]Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47–66, 2017.DOI
  6. [6]Elie Abboud and Noga Ron-Zewi. Finer-grained reductions in fine-grained hardness of approximation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP), volume 297 of Leibniz International Proceedings in Informatics, pages 7:1–7:17, 2024.arxiv.org/abs/2311.00798
  7. [7]Pankaj K. Agarwal and R. Sharathkumar. Streaming algorithms for extent problems in high dimensions. Algorithmica, 72(1):83–98, 2015. Preliminary version in SODA 2010.
  8. [8]Jackson Bibbens, Levi Borevitz, and Samuel McCauley. Space-efficient text indexing with mismatches using function inversion. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 1061–1072, 2026.
  9. [9]Lotte Blank, Sergio Cabello, Mohammad Taghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, André Nusser, Jeff M. Phillips, and Jonas Sauer. The expiration streaming model: Diameter, k-center, counting, sampling, and friends. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 374 of Leibniz International Proceedings in Informatics, pages 37:1–37:24, 2026.arxiv.org/abs/2509.07587
  10. [10]Kiarash Banihashem, Jeff Giliberti, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic diameter in high-dimensions against adaptive adversary and beyond. In Advances in Neural Information Processing Systems (NeurIPS), volume 38, 2025. Full version: arXiv:2511.01065.arxiv.org/abs/2511.01065
  11. [11]Kiarash Banihashem, Jeff Giliberti, Prashant Gokhale, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Yuhao Liu, Morteza Monemizadeh, and Sandeep Silwal. Adversarially robust approximate furthest neighbor. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 6281–6297, 2026.arxiv.org/abs/2605.16618
  12. [12]Gabriel Bathie and Guillaume Lagarde. A (1 + ε)-approximation for ultrametric embedding in subquadratic time. Proceedings of the AAAI Conference on Artificial Intelligence, 39(15):15516–15523, 2025.DOI
  13. [13]Timothy M. Chan. Dynamic streaming algorithms for epsilon-kernels. In 32nd International Symposium on Computational Geometry (SoCG), volume 51 of Leibniz International Proceedings in Informatics, pages 27:1–27:11, 2016.DOI
  14. [14]Tobias Christiani. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 31–46, 2017.
  15. [15]Timothy M. Chan and Vinayak Pathak. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. Computational Geometry, 47(2):240–247, 2014. Preliminary version in WADS 2011.
  16. [16]Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. Full version: arXiv:1811.12017.arxiv.org/abs/1811.12017
  17. [17]Ashish Goel, Piotr Indyk, and Kasturi Varadarajan. Reductions among high dimensional proximity problems. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 769–778, 2001.
  18. [18]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988.
  19. [19]Magnús M. Halldórsson, Nicolaos M atsakis, and Pavel Veselý. Streaming diameter of high-dimensional points. In 33rd Annual European Symposium on Algorithms (ESA), volume 351 of Leibniz International Proceedings in Informatics, pages 58:1–58:10, 2025.arxiv.org/abs/2505.16720
  20. [20]Sariel Har-Peled and Mitchell Jones. Journey to the center of the point set. In 35th International Symposium on Computational Geometry (SoCG), volume 129 of Leibniz International Proceedings in Informatics, pages 41:1–41:14, 2019.
  21. [21]Sariel Har-Peled and Timothy Zhou. Improved approximation algorithms for Tverberg partitions. In 29th Annual European Symposium on Algorithms (ESA), volume 204 of Leibniz International Proceedings in Informatics, pages 51:1–51:15, 2021.
  22. [22]David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127–151, 1987.DOI
  23. [23]Piotr Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 539–545, 2003.
  24. [24]Cheng Jiang, Yinchen Liu, and Huacheng Yu. Turnstile streaming algorithms might (still) as well be linear sketches, for polynomial-length streams, 2026. Version 2, October 30, 2026; accepted to FOCS 2026.arxiv.org/abs/2604.22052
  25. [25]John Kuszmaul and William Kuszmaul. Dynamic and optimal function inversion in the small-time regime, 2026.arxiv.org/abs/2609.20240
  26. [26]Sanjeev Khanna, Ashwin Padaki, Krish Singal, and Erik Waingarten. A polynomial space lower bound for diameter estimation in dynamic streams. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), 2025. Full version: arXiv:2510.04918.arxiv.org/abs/2510.04918
  27. [27]Samuel McCauley. Improved space-efficient approximate nearest neighbor search using function inversion. In 32nd Annual European Symposium on Algorithms (ESA), volume 308 of Leibniz International Proceedings in Informatics, pages 88:1–88:19, 2024.arxiv.org/abs/2407.02468
  28. [28]Ashwin Padaki, Krish Singal, and Erik Waingarten. A near-optimal space lower bound for Euclidean diameter estimation in dynamic streams, 2026. arXiv:2609.19089.arxiv.org/abs/2609.19089
  29. [29]Mathieu Vannimmen. From function inversion to preimage reporting, 2026. Version 1, November 6, 2026.arxiv.org/abs/2611.09656
  30. [30]Vladimir N. Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971.
  31. [31]Alexander Wei. Optimal Las Vegas approximate near neighbors in ℓp. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1794–1813, 2019.

Paper details

vlnc:W_tctybskr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI Astra, Gemini Argon

View statement
Looking for related papers…
Contents