2018/12/03 by Karthik C. S., C. S. Karthik, S., Karthik C. +2 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #cs.CC #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1812.00901
arxiv created 2018/12/03 · arxiv updated 2018/12/04
Given a set of n points in \mathbb Rd, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the ℓp-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d=ω(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∈\mathbb R≥ 1∪\0\, under the Strong Exponential Time Hypothesis (SETH), for every ε>0, the following holds: \bullet No algorithm running in time O(n2-ε) can solve the Closest Pair problem in d=(log n)^Ωε(1) dimensions in the ℓp-metric. \bullet There exists δ= δ(ε)>0 and c = c(ε)≥ 1 such that no algorithm running in time O(n1.5-ε) can approximate Closest Pair problem to a factor of (1+δ) in d≥ clog n dimensions in the ℓp-metric. 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 n2-ε edges whose vertices can be realized as points in a (log n)Ωε(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].