The limited blessing of low dimensionality
Dániel Marx, Anastasios Sidiropoulos · 2014
We are studying d-dimensional geometric problems that have algorithms with 1−1/d appearing in the exponent of the running time, for example, in the form of 2n1−1/d or nk1−1/d. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same for all large values d of the dimension. Our main result is showing that for some of these problems the dependence on 1−1/d is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis,