CS Paper Radar

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

Mohammad Hajiaghayi, Morteza Monemizadeh

cs.DS ·submitted 2026-11-12 16:32 UTC · v3

Abstract

We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $δ$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/δ))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/δ))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 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(2nt/δ)$. With probability at least $1-δ$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices. A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$

cs.CC ·2026-10-27 ·Eric Binnendyk
theory similarity 0.69
Abstract

It is known that the problem of recognizing the existence of a unit-distance realization in $\mathbb{Z}^d$ for a graph $G$ is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of $2^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(n^{2/3})}$ in $\mathbb{Z}^3$, and give an upper bound of $2^{O(n^{(d-1)/d} (\log n)^2)}$ for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of $\tildeΩ(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.

0.27

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.67
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

Fast Geometric Spanners via Approximate Nearest Neighbor Search

cs.DS cs.CG ·2026-09-22 ·Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
similarity 0.66
Abstract

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $Ω(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

0.07

Subexponential Algorithms for Continuous Euclidean $k$-Means in Subpolylogarithmic Dimension

cs.CG cs.DS ·2026-11-19 ·Junqi Tan
similarity 0.66
Abstract · 22 pages

Given $n$ points in $\mathbb{Q}^d$ and an integer $k$, the continuous Euclidean $k$-means problem asks for $k$ centers in $\mathbb{R}^d$ that minimize the sum of squared distances from the input points to their nearest centers. In one dimension, the problem can be solved in polynomial time by dynamic programming. In higher dimensions, the algorithm of Inaba, Katoh, and Imai [SoCG 1994] runs in polynomial time when both $k$ and $d$ are fixed. Mahajan, Nimbhorkar, and Varadarajan [TCS 2012] showed that the problem is NP-hard even in the plane when $k$ is part of the input, answering a question of Dasgupta [2008]. In this paper, we give a deterministic exact algorithm for continuous Euclidean $k$-means. For arbitrary $k$ and $d=(\log n)^{o(1)}$, the algorithm runs in $O^*(2^{o(n)})$ time and uses polynomial space. Aman, Karthik C. S., and Punna [ESA 2024] asked whether the $2^n$ time bound for Euclidean $k$-means can be improved in high dimensions. Our result gives an affirmative answer to the corresponding question in subpolylogarithmic dimension.

0.17

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.65
Abstract

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

0.18

Approximate Nearest Neighbor in Ultra-High Dimensional $\ell_\infty$

cs.DS ·2026-09-08 ·Nathan White, Tian Zhang
theory similarity 0.65
Abstract

We study the approximate nearest neighbor problem under $\ell_\infty$ in the ultra-high dimensional setting where the dimension $d$ is significantly larger than the number of points $n$. Thus, we desire data structures with no dependence on $d$ in the query time. [Herold-Nanongkai-Spoerhase-Varma-Wu, SoCG 2025] introduce this problem and give data structures in $\ell_p$: for $p=1,2$, they give $(1+\varepsilon)$-approximation data structures with space $\tilde{O}(n\log d/\text{poly}(\varepsilon))$ and query time $\tilde{O}(n/\text{poly}(\varepsilon))$. Since any data structure must have query time $Ω(\min \{n,d\})$, this query time is nearly tight. However, their results are inefficient for $\ell_\infty$, with query time $Ω(nd)$. In order to handle the challenges of $\ell_\infty$, we introduce a notion of subset embeddings, which embed points by simply selecting a subset of dimensions. In particular, we show one may preserve all pairwise distances of an $n$ point dataset up to a factor of $O(c)$ by computing distances on only $n^{1+1/c}$ coordinates. We also show a matching lower bound: for any $c > 1$, there exists a set of $n$ points in $\mathbb{R}^{d}$ such that any subset embedding for the set with approximation $c$ must have at least $n^{1+Ω(1/c)}$ coordinates. Using our subset embeddings, we give data structures for approximate nearest neighbor in $\ell_\infty$ with space $O(n^2\log d)$, query time $\tilde{O}(n^{1+1/c})$, and approximation $O(c\log\log n)$ for any $c \geq 1$. Finally, we give another data structure for the approximate nearest neighbor under $\ell_\infty$ with the same space and query time as our subset embedding approach, but with approximation $O(c^{\log_2 3}) \approx O(c^{1.58})$. This allows us to achieve $O(1)$-approximation with query time e.g.~$n^{1.01}$

0.13

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.65
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Point and Line Nearest-Neighbor Searching in 3-Space

cs.CG ·2026-10-02 ·Pankaj K. Agarwal, Esther Ezra, Micha Sharir
similarity 0.64
Abstract

This paper presents data structures for nearest-neighbor (NN) searching problems involving points, lines, segments, and triangles in 3-space, achieving significantly better performance than the previously best-known results for these problems. For example, we present a linear-size data structure for answering NN queries with lines or segments amid $n$ points in 3-space with $O^*(n^{1/2})$ query time (where the $O^*(\cdot)$ notation hides subpolynomial factors). We also present a data structure of $O^*(n^4)$ size that answers such queries in $O^*(1)$ time. For the converse problem, in which we seek the nearest neighbor of a query point amid $n$ lines, segments, or triangles in 3-space, we present a linear-size data structure with $O^*(n^{2/3})$ query time. These results constitute a significant improvement over previous solutions. We obtain improved solutions for the two extreme regimes of (near-)linear storage and of fast query time. These results also yield trade-off bounds between the query time and the size of the data structure. Our results rely on several combinatorial and algorithmic results on arrangements of surfaces in 3-space and 4-space, particularly on recent results on vertical decompositions of substructures in such arrangements established by the authors.

0.17