On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry
share
Point location problems for n points in d-dimensional Euclidean space (and ℓ_p spaces more generally) have typically had two kinds of running-time solutions: * (Nearly-Linear) less than d^poly(d)· n ^O(d) n time, or * (Barely-Subquadratic) f(d) · 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, finding a Closest Pair among n points in R^d is nearly-linear, solvable in 2^O(d)· n ^O(1) n time, while known algorithms for Furthest Pair (the diameter of the point set) are only barely-subquadratic, requiring Ω(n^2-1/Θ(d)) time. Why do these proximity problems have such different time complexities? Is there a barrier to obtaining nearly-linear algorithms for problems which are currently only barely-subquadratic? We give a novel exact and deterministic self-reduction for the Orthogonal Vectors problem on n vectors in {0,1}^d to n vectors in Z^ω( d) that runs in 2^o(d) time. As a consequence, barely-subquadratic problems such as Euclidean diameter, Euclidean bichromatic closest pair, ray shooting, and incidence detection do not have O(n^2-ϵ) time algorithms (in Turing models of computation) for dimensionality d = ω( n)^2, unless the popular Orthogonal Vectors Conjecture and the Strong Exponential Time Hypothesis are false. That is, while poly-log-log-dimensional Closest Pair is in n^1+o(1) time, the analogous case of Furthest Pair can encode larger-dimensional problems conjectured to require n^2-o(1) time. We also show that the All-Nearest Neighbors problem in ω( n) dimensions requires n^2-o(1) time to solve, assuming either of the above conjectures.
READ FULL TEXT