Algorithmic interpretations of fractal dimension

DOI10.4230/LIPICS.SOCG.2017.58MaRDI QIDQ4580136zbMATH OpenOpenAlexFDO

Authors Anastasios Sidiropoulos, V. Sridhar

Publication date 13 August 2018

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

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)

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.

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

Cited in

(10)

• An algorithm for computing the fractal dimension of waveforms
• scientific article; zbMATH DE number 5269064 (Why is no real title available?)
• Fractal Intersections and Products via Algorithmic Dimension
• Fractal dimension and lower bounds for geometric problems
• ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
• scientific article; zbMATH DE number 4121282 (Why is no real title available?)
• scientific article; zbMATH DE number 2216397 (Why is no real title available?)
• scientific article; zbMATH DE number 7236474 (Why is no real title available?)
• scientific article; zbMATH DE number 7163811 (Why is no real title available?)
• A Computer Algorithm for Determining the Hausdorff Dimension of Certain Fractals

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)