Given a set of n points in \mathbb R^d, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the \ell_p-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d=\omega(\log n) was raised as an open question in recent works (Abboud-Rubinstein-Williams [FOCS'17], Williams [SODA'18], David-Karthik-Laekhanukit [SoCG'18]).
In this paper, we show that for every p\in\mathbb R_{\ge 1}\cup\{0\}, under the Strong Exponential Time Hypothesis (SETH), for every \varepsilon>0, the following holds:
\bullet No algorithm running in time O(n^{2-\varepsilon}) can solve the Closest Pair problem in d=(\log n)^{\Omega_{\varepsilon}(1)} dimensions in the \ell_p-metric.
\bullet There exists \delta = \delta(\varepsilon)>0 and c = c(\varepsilon)\ge 1 such that no algorithm running in time O(n^{1.5-\varepsilon}) can approximate Closest Pair problem to a factor of (1+\delta) in d\ge c\log n dimensions in the \ell_p-metric.
In particular, our first result is shown by establishing the computational equivalence of the bichromatic Closest Pair problem and the (monochromatic) Closest Pair problem (up to n^{\varepsilon} factor in the running time) for d=(\log n)^{\Omega_\varepsilon(1)} dimensions.
Additionally, under SETH, we rule out nearly-polynomial factor approximation algorithms running in subquadratic time for the (monochromatic) Maximum Inner Product problem where we are given a set of n points in n^{o(1)}-dimensional Euclidean space and are required to find a pair of distinct points in the set that maximize the inner product.
At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on n vertices with n^{2-\varepsilon} edges whose vertices can be realized as points in a (\log n)^{\Omega_\varepsilon(1)}-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Miccancio-Sudan [IEEE Trans. Inf. Theory'03].
