arXiv:2611.17050 · v1

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

首次提交 2026-11-13 00:32

版本更新 2026-11-13 00:32

雷达观测 2026-11-13 14:15

摘要

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. 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 $\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θ)}$ overhead of the algorithm that Andoni, Jiang, and Zharkov~\cite{ajz2026} (STOC'26) for Hamming approximation $2-θ$ to $n^{O(θ)+o(1)}$.