  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 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. We define the fractal dimension of some
metric space to be the infimum $\delta>0$, such that for any $\epsilon > 0$,
for any ball $B$ of radius $r\geq 2\epsilon$, and for any $\epsilon $-net $N$
(that is, for any maximal $\epsilon $-packing), we have $|B\cap
N|=O((r/\epsilon)^\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 fixed-parameter algorithms, approximation schemes, and spanner
constructions. Interestingly, the dependence of the performance of these
algorithms on the fractal dimension nearly matches the currently best-known
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.
