Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH
For computational geometers, this establishes tight lower bounds for fundamental problems in high dimensions, confirming that subquadratic algorithms are impossible under SETH.
The paper proves that, under SETH, several geometric problems (Furthest Pair, Bichromatic Closest Pair, Maximum Inner Product, Hopcroft's Problem) require n^{2-o(1)} time for any superconstant dimension d=ω(1), extending a previous lower bound that only held for d=2^{Θ(log^* n)}. This shows that the dependence on dimension in the best known algorithms is essentially unavoidable.
Several fundamental problems in computational geometry admit algorithms with running time $f(d) \cdot n^{2-Θ(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^{Θ(\log^* n)}$. We extend this lower bound to all efficiently constructible dimensions $d=ω(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.