Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH (opens in new tab)

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...