Item

Abstract

Fine-grained complexity theory is the area of theoretical computer science
that proves conditional lower bounds based on the Strong Exponential Time
Hypothesis and similar conjectures. This area has been thriving in the last
decade, leading to conditionally best-possible algorithms for a wide variety of
problems on graphs, strings, numbers etc. This article is an introduction to
fine-grained lower bounds in computational geometry, with a focus on lower
bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis.
Specifically, we discuss conditional lower bounds for nearest neighbor search
under the Euclidean distance and Fr\'echet distance.