On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry

Point location problems for $n$ points in $d$-dimensional Euclidean space (and $\ell_p$ spaces more generally) have typically had two kinds of running-time solutions: * (Nearly-Linear) less than $d^{poly(d)} \cdot n \log^{O(d)} n$ time, or * (Barely-Subquadratic) $f(d) \cdot n^{2-1/Θ(d)}$ time, for various $f$. For small $d$ and large $n$, "nearly-linear" running times are generally feasible, while "barely-subquadratic" times are generally infeasible. For example, in the Euclidean metric, ...