Abstract
We study algorithmic problems on subsets of Euclidean space of low fractal dimension. These spaces are the subject of intensive study in various branches of mathematics, including geometry, topology, and measure theory. There are several wellstudied 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. We define the fractal dimension of some metric space to be the infimum delta>0, such that for any eps>0, for any ball B of radius r >= 2eps, and for any epsnet N, we have B cap N=O((r/eps)^delta).
Using this definition we obtain faster algorithms for a plethora of classical problems on sets of low fractal dimension in Euclidean space. Our results apply to exact and fixedparameter algorithms, approximation schemes, and spanner constructions. Interestingly, the dependence of the performance of these algorithms on the fractal dimension nearly matches the currently bestknown dependence on the standard Euclidean dimension. Thus, when the fractal dimension is strictly smaller than the ambient dimension, our results yield improved solutions in all of these settings.
We remark that our definition of fractal definition is equivalent up to constant factors to the wellstudied notion of doubling dimension.
However, in the problems that we consider, the dimension appears in the exponent of the running time, and doubling dimension is not precise enough for capturing the best possible such exponent for subsets of Euclidean space. Thus our work is orthogonal to previous results on spaces of low doubling dimension; while algorithms on spaces of low doubling dimension seek to extend results from the case of low dimensional Euclidean spaces to more general metric spaces, our goal is to obtain faster algorithms for special pointsets in Euclidean space.
BibTeX  Entry
@InProceedings{sidiropoulos_et_al:LIPIcs:2017:7212,
author = {Anastasios Sidiropoulos and Vijay Sridhar},
title = {{Algorithmic Interpretations of Fractal Dimension}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {58:158:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7212},
URN = {urn:nbn:de:0030drops72126},
doi = {10.4230/LIPIcs.SoCG.2017.58},
annote = {Keywords: fractal dimension, exact algorithms, fixed parameter tractability, approximation schemes, spanners}
}
Keywords: 

fractal dimension, exact algorithms, fixed parameter tractability, approximation schemes, spanners 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 