## 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(n^{2−ε}) 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(n^{1.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 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−ε} 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 language | English (US) |
---|---|

Title of host publication | 10th Innovations in Theoretical Computer Science, ITCS 2019 |

Editors | Avrim Blum |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770958 |

DOIs | |

State | Published - Jan 1 2019 |

Externally published | Yes |

Event | 10th Innovations in Theoretical Computer Science, ITCS 2019 - San Diego, United States Duration: Jan 10 2019 → Jan 12 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 124 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 10th Innovations in Theoretical Computer Science, ITCS 2019 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 1/10/19 → 1/12/19 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

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