Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH

Abstract

Several fundamental problems in computational geometry admit algorithms with running time $f(d)\cdot n^{2-\Theta (1/d)}$ for $n$ points in $d$ dimensions, making them among the most prominent examples of barely subquadratic computation. Notable members of this class include Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Innter Product, and Hopcroft's Problem. Chen [Theory Comput. 2020] proved that, assuming the Strong Exponential Time Hypothesis (SETH), these problems require $n^{2-o(1)}$ time when the dimension satisfies $d=2^{\Theta ({\log }^{\ast }n)}$. We extend this lower bound to all efficiently constructible dimensions $d=\omega (1)$. Thus, assuming SETH, the dependence of the best known algorithms on the dimension is essentially unavoidable. The proof utilizes techniques in OpenAI's recent disproof of the Erdos unit distance conjecture. The proof was initially discovered by ChatGPT 5.5 Pro. The authors have validated and substantially edited the proof to improve the presentation.

arXiv comment44 pages, 4 figures