精选理由
这篇论文把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单位距离猜想的反证方法。
AI 翻译 · 中文
该论文证明在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单位距离猜想的反证方法。
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 c…