On closest pair in Euclidean metric: Monochromatic is as hard as bichromatic

C. S. Karthik, Pasin Manurangsi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Given a set of n points in ℝd, 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 ϵ ℝ≥1 ∪ {0}, under the Strong Exponential Time Hypothesis (SETH), for every ε > 0, the following holds: ▬ No algorithm running in time O(n2−ε) can solve the Closest Pair problem in d = (log n)Ωε(1) dimensions in the ℓp-metric. ▬ 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 ≥ c log n dimensions in the ℓ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ε factor in the running time) for d = (log n)Ωε(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 no(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 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].

Original languageEnglish (US)
Title of host publication10th Innovations in Theoretical Computer Science, ITCS 2019
EditorsAvrim Blum
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770958
DOIs
StatePublished - Jan 1 2019
Externally publishedYes
Event10th Innovations in Theoretical Computer Science, ITCS 2019 - San Diego, United States
Duration: Jan 10 2019Jan 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume124
ISSN (Print)1868-8969

Conference

Conference10th Innovations in Theoretical Computer Science, ITCS 2019
Country/TerritoryUnited States
CitySan Diego
Period1/10/191/12/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Bichromatic Closest Pair
  • Closest Pair
  • Contact Dimension
  • Fine-Grained Complexity

Fingerprint

Dive into the research topics of 'On closest pair in Euclidean metric: Monochromatic is as hard as bichromatic'. Together they form a unique fingerprint.

Cite this