{"arxiv_id":"2611.17050","title":"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<\\sqrt2$, we maintain an actual factor-$c$ 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 $n$ bounds the number of active points. The update exponent improves Indyk's algorithm~\\cite{indyk} (SODA'03) bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\\sqrt2$ with update time polynomial in $d$ and $\\log n$. All these guarantees hold against adaptive updates, even when every previous random choice is exposed.\n  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.\n  The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\\sqrt2-\\varepsilon$, the diameter time is $n^{1+O(\\varepsilon)}$, and the query time is $n^{O(\\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors. On binary points, this improves the $n^{O(\\sqrt\\theta)}$ overhead of the algorithm that Andoni, Jiang, and Zharkov~\\cite{ajz2026} (STOC'26) for Hamming approximation $2-\\theta$ to $n^{O(\\theta)+o(1)}$.","primary_cat":"cs.DS","cross_cats":[],"submitted_at":"2026-11-12T16:32:35+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"CONDITIONAL","confidence":"MODERATE","one_line_summary":"Fully dynamic diameter approximation below sqrt(2) is maintained with update exponent 2/c^2-1 and an exactly sqrt(2) endpoint with poly(d, log n) updates, via a lifted-centerpoint variance identity.","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.17050","verdict":"/api/v1/verdicts/2611.17050"}}