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

Ryan Williams

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