# On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry

arXiv: https://arxiv.org/abs/1709.05282 · HTML: https://mlsanity.com/paper/1709.05282/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2017.

## Built on by (most cited first, 6 of 6)

- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [Can You Solve Closest String Faster than Exhaustive Search?](https://mlsanity.com/paper/2305.16878/) (2023)
- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)

## Abstract (arXiv)

Point location problems for n points in d-dimensional Euclidean space (and ℓp spaces more generally) have typically had two kinds of running-time solutions: * (Nearly-Linear) less than dpoly(d) · n logO(d) n time, or * (Barely-Subquadratic) f(d) · n2-1/Theta(d) time, for various f. For small d and large n, "nearly-linear" running times are generally feasible, while "barely-subquadratic" times are generally infeasible. For example, in the Euclidean metric, finding a Closest Pair among n points in mathbb Rd is nearly-linear, solvable in 2O(d) · n logO(1) n time, while known algorithms for Furthest Pair (the diameter of the point set) are only barely-subquadratic, requiring Omega(n2-1/Theta(d)) time. Why do these proximity problems have such different time complexities? Is there a barrier to obtaining nearly-linear algorithms for problems which are currently only barely-subquadratic? We give a novel exact and deterministic self-reduction for the Orthogonal Vectors problem on n vectors in 0,1d to n vectors in mathbb Zω(log d) that runs in 2o(d) time. As a consequence, barely-subquadratic problems such as Euclidean diameter, Euclidean bichromatic closest pair, ray shooting, and incidence detection do not have O(n2-ε) time algorithms (in Turing models of computation) for dimensionality d = ω(log log n)2, unless the popular Orthogonal Vectors Conjecture and the Strong Exponential Time Hypothesis are false. That is, while poly-log-log-dimensional Closest Pair is in n1+o(1) time, the analogous case of Furthest Pair can encode larger-dimensional problems conjectured to require n2-o(1) time. We also show that the All-Nearest Neighbors problem in ω(log n) dimensions requires n2-o(1) time to solve, assuming either of the above conjectures.