Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH

Barna Saha, Yinzhan Xu, Christopher Ye

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 pro…