Self-similar fractals: An algorithmic point of view

Autor: Kai Zhang, Li-Feng Xi, Qin Wang
Rok vydání: 2014
Předmět:
Zdroj: Science China Mathematics. 57:755-766
ISSN: 1869-1862
1674-7283
DOI: 10.1007/s11425-013-4767-x
Popis: This paper studies the self-similar fractals with overlaps from an algorithmic point of view. A decidable problem is a question such that there is an algorithm to answer “yes” or “no” to the question for every possible input. For a classical class of self-similar sets {Eb.d}b,d where Eb.d = ∪i=1n (Eb,d/d + bi) with b = (b1,…, bn) ∈ ℚn and d ∈ ℕ ∩ [n,∞), we prove that the following problems on the class are decidable: To test if the Hausdorff dimension of a given self-similar set is equal to its similarity dimension, and to test if a given self-similar set satisfies the open set condition (or the strong separation condition). In fact, based on graph algorithm, there are polynomial time algorithms for the above decidable problem.
Databáze: OpenAIRE
Externí odkaz: