Georgia Institute of Technology College of Sciences

The computational complexity of many geometric problems depends on the dimension of the input space. We study algorithmic problems on spaces of low fractal dimension. There are several well-studied notions of fractal dimension for sets and measures in Euclidean space. We consider a definition of fractal dimension for finite metric spaces, which agrees with standard notions used to empirically estimate the fractal dimension of various sets. When the fractal dimension of the input is lower than the ambient dimension, we obtain faster algorithms for a plethora of classical problems, including TSP, Independent Set, R-Cover, and R-Packing. Interestingly, the dependence of the performance of these algorithms on the fractal dimension closely resembles the currently best-known dependence on the standard Euclidean dimension. For example, our algorithm for TSP has running time 2^O(n^(1-1/delta) * log(n)), on sets of fractal dimension delta; in comparison, the best-known algorithm for sets in d-dimensional Euclidean space has running time 2^O(n^(1-1/d)).