×

Optimal dynamic box-counting algorithm. (English) Zbl 1208.28004

Summary: An optimal box-counting algorithm for estimating the fractal dimension of a nonempty set which changes over time is given. This nonstationary environment is characterized by the insertion of new points into the set and in many cases the deletion of some existing points from the set. In this setting, the issue at hand is to update the box-counting result at appropriate time intervals with low computational cost. The proposed algorithm tackles the dynamic box-counting problem by using computational geometry methods. In particular, we use a sequence of compressed Box Quadtrees to store the data points. This storage permits the fast and efficient application of our box-counting approach to compute what we call the ”dynamic fractal dimension”. For a nonempty set of points in the d-dimensional space \(\mathbb R^{d}\) (for constant \(d \geq 1)\), the time complexity of the proposed algorithm is shown to be \(O(n \log n)\) while the space complexity is \(O(n)\), where n is the number of considered points. In addition, we show that the time complexity of an insertion, or a deletion is \(O(\log n)\), and that the above time and space complexity is optimal. Experimental results of the proposed approach illustrated on the well-known and widely studied Hénon map are presented.

MSC:

28A80 Fractals
37C45 Dimension theory of smooth dynamical systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho A. V., The Design and Analysis of Computer Algorithms (1974) · Zbl 0326.68005
[2] DOI: 10.1007/BF01608556 · Zbl 0576.58018 · doi:10.1007/BF01608556
[3] DOI: 10.1016/0375-9601(90)90844-E · doi:10.1016/0375-9601(90)90844-E
[4] DOI: 10.1016/0010-4655(96)00080-X · Zbl 0928.65155 · doi:10.1016/0010-4655(96)00080-X
[5] DOI: 10.1016/0375-9601(89)90854-2 · doi:10.1016/0375-9601(89)90854-2
[6] Mandelbrot B. B., The Fractal Geometry of Nature (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.