Algorithmic interpretations of fractal dimension

DOI10.4230/LIPICS.SOCG.2017.58zbMATH Open1432.68527arXiv1703.09324OpenAlexW2604499455MaRDI QIDQ4580136FDOQ4580136

Authors: Anastasios Sidiropoulos, V. Sridhar 

Publication date: 13 August 2018

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 $epsilon>0$, for any ball $B$ of radius $rgeq2epsilon$, and for any $epsilon$-net $N$ (that is, for any maximal $epsilon$-packing), we have $|BcapN|=O((r/epsilon{)}^{d}elta)$. 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.

Full work available at URL: https://arxiv.org/abs/1703.09324

Recommendations

• Fractal dimension and lower bounds for geometric problems
• scientific article; zbMATH DE number 7236474
• Fractal Intersections and Products via Algorithmic Dimension
• Proximity algorithms for nearly doubling spaces
• Proximity algorithms for nearly-doubling spaces

zbMATH Keywords

approximation schemesexact algorithmsfractal dimensionfixed parameter tractabilityspanners

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Fractals (28A80) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (10)

• Fractal Intersections and Products via Algorithmic Dimension
• Fractal dimension and lower bounds for geometric problems
• ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Computer Algorithm for Determining the Hausdorff Dimension of Certain Fractals
• Title not available (Why is that?)
• An algorithm for computing the fractal dimension of waveforms

This page was built for publication: Algorithmic interpretations of fractal dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580136)