这篇论文把SETH下界从特殊维度扩展到所有可构造维度，说明计算几何经典问题的维度依赖几乎无法消除。
该论文证明在SETH假设下，Furthest Pair、Bichromatic Closest Pair等几何问题在d=ω(1)维度时需n^{2-o(1)}时间。此前Chen (2020)只对d=2^{Θ(log^* n)}维度成立。新结果将所有可构造维度纳入下界，意味着现有f(d)·n^{2-Θ(1/d)}算法的维度依赖本质上不可避免。证明技术利用了OpenAI近期对Erdos单位距离猜想的反证方法。
Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH
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.