Abstract
Given a set of n points in R^d, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the l_pmetric. Closest Pair is a fundamental problem in Computational Geometry and understanding its finegrained complexity in the Euclidean metric when d=omega(log n) was raised as an open question in recent works (AbboudRubinsteinWilliams [FOCS'17], Williams [SODA'18], DavidKarthikLaekhanukit [SoCG'18]).
In this paper, we show that for every p in R_{>= 1} cup {0}, under the Strong Exponential Time Hypothesis (SETH), for every epsilon>0, the following holds:
 No algorithm running in time O(n^{2epsilon}) can solve the Closest Pair problem in d=(log n)^{Omega_{epsilon}(1)} dimensions in the l_pmetric.
 There exists delta = delta(epsilon)>0 and c = c(epsilon)>= 1 such that no algorithm running in time O(n^{1.5epsilon}) can approximate Closest Pair problem to a factor of (1+delta) in d >= c log n dimensions in the l_pmetric.
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^{epsilon} factor in the running time) for d=(log n)^{Omega_epsilon(1)} dimensions.
Additionally, under SETH, we rule out nearlypolynomial 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^{2epsilon} edges whose vertices can be realized as points in a (log n)^{Omega_epsilon(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 DumerMiccancioSudan [IEEE Trans. Inf. Theory'03].
BibTeX  Entry
@InProceedings{cs_et_al:LIPIcs:2018:10110,
author = {Karthik C. S. and Pasin Manurangsi},
title = {{On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {17:117:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10110},
URN = {urn:nbn:de:0030drops101100},
doi = {10.4230/LIPIcs.ITCS.2019.17},
annote = {Keywords: Closest Pair, Bichromatic Closest Pair, Contact Dimension, FineGrained Complexity}
}
Keywords: 

Closest Pair, Bichromatic Closest Pair, Contact Dimension, FineGrained Complexity 
Collection: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 