Title: Fractal dimension and lower bounds for geometric problems,
Abstract: We study the complexity of geometric problems on spaces of low fractal
dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that
several problems admit improved solutions when the input is a pointset in
Euclidean space with fractal dimension smaller than the ambient dimension. In
this paper we prove nearly-matching lower bounds, thus establishing
nearly-optimal bounds for various problems as a function of the fractal
dimension.
More specifically, we show that for any set of $n$ points in $d$-dimensional
Euclidean space, of fractal dimension $\delta\in (1,d)$, for any $\epsilon >0$
and $c\geq 1$, any $c$-spanner must have treewidth at least $\Omega \left(
\frac{n^{1-1/(\delta - \epsilon)}}{c^{d-1}} \right)$, matching the previous
upper bound. The construction used to prove this lower bound on the treewidth
of spanners can also be used to derive lower bounds on the running time of
algorithms for various problems, assuming the Exponential Time Hypothesis. We
provide two prototypical results of this type. For any $\delta \in (1,d)$ and
any $\epsilon >0$ we show that:
1) $d$-dimensional Euclidean TSP on $n$ points with fractal dimension at most
$\delta$ cannot be solved in time $2^{O\left(n^{1-1/(\delta - \epsilon)}
\right)}$. The best-known upper bound is $2^{O(n^{1-1/\delta} \log n)}$.
2) The problem of finding $k$-pairwise non-intersecting $d$-dimensional unit
balls/axis parallel unit cubes with centers having fractal dimension at most
$\delta$ cannot be solved in time $f(k)n^{O \left(k^{1-1/(\delta -
\epsilon)}\right)}$ for any computable function $f$. The best-known upper bound
is $n^{O(k^{1-1/\delta} \log n)}$.
The above results nearly match previously known upper bounds from
[Sidiropoulos & Sridhar, SoCG 2017], and generalize analogous lower bounds for
the case of ambient dimension due to [Marx & Sidiropoulos, SoCG 2014].