License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.58
URN: urn:nbn:de:0030-drops-72126
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7212/
Go to the corresponding LIPIcs Volume Portal

Sidiropoulos, Anastasios ; Sridhar, Vijay

Algorithmic Interpretations of Fractal Dimension

pdf-format:
LIPIcs-SoCG-2017-58.pdf (0.6 MB)

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 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 eps>0, for any ball B of radius r >= 2eps, and for any eps-net 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 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.

We remark that our definition of fractal definition is equivalent up to constant factors to the well-studied 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:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7212},
  URN =		{urn:nbn:de:0030-drops-72126},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI