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 nearlymatching lower bounds, thus establishing nearlyoptimal bounds for various problems as a function of the fractal dimension.
More specifically, we show that for any set of n points in ddimensional Euclidean space, of fractal dimension delta in (1,d), for any epsilon>0 and c >= 1, any cspanner must have treewidth at least Omega(n^{11/(delta  epsilon)} / c^{d1}), 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, ddimensional Euclidean TSP on n points with fractal dimension at most delta cannot be solved in time 2^{O(n^{11/(delta  epsilon)})}. The bestknown upper bound is 2^{O(n^{11/delta} log n)}.
 For any delta in (1,d) and any epsilon >0, the problem of finding kpairwise nonintersecting ddimensional unit balls/axis parallel unit cubes with centers having fractal dimension at most delta cannot be solved in time f(k)n^{O (k^{11/(delta  epsilon)})} for any computable function f. The bestknown upper bound is n^{O(k^{11/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].
BibTeX  Entry
@InProceedings{sidiropoulos_et_al:LIPIcs:2018:8783,
author = {Anastasios Sidiropoulos and Kritika Singhal and Vijay Sridhar},
title = {{Fractal Dimension and Lower Bounds for Geometric Problems}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {70:170:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8783},
URN = {urn:nbn:de:0030drops87831},
doi = {10.4230/LIPIcs.SoCG.2018.70},
annote = {Keywords: fractal dimension, treewidth, spanners, lower bounds, exponential time hypothesis}
}
Keywords: 

fractal dimension, treewidth, spanners, lower bounds, exponential time hypothesis 
Collection: 

34th International Symposium on Computational Geometry (SoCG 2018) 
Issue Date: 

2018 
Date of publication: 

08.06.2018 