Computability of Self-Similar Sets
Most fractals used in computer graphics and in similar areas are self-similar sets, i.e., each such fractal can be described as a unique non-empty compact solution of the equation \(X=T_0(X)\cup \ldots\cup T_{m-1}(X)\), where \(T_i\) are affine contractions. For such self-similar fractals, it was proven that the set \(X\) is recursive in the sense that the function \(x\to d(x,X)\), which describes a distance \(d(x,X)\) from an arbitrary point \(x\) to this set \(X\), is computable. In some applications, non-linear transformations are natural. In such applications, it makes sense to consider more general self-similar sets -- namely, the solution of the above equation for contractions \(T_i\) which are computable but not necessarily affine. The author proves that such general self-similar sets are also recursive. The proof is based on the fact that the mapping \(X\to T_0(X)\cup \ldots\cup T_{m-1}(X)\) is a (constructive) contraction in Hausdorff metric and therefore the desired limit can be computed by using a constructive version of a fixed point theorem for contractions in a metric space.
- A continuous real-valued function on E^n almost everywhere 1-1
- Composition of contractions
- Computability on computable metric spaces
- Computing with infinite objects
- scientific article; zbMATH DE number 3964277 (Why is no real title available?)
- scientific article; zbMATH DE number 2013199 (Why is no real title available?)
- On the structure of self-similar fractals
- On the structure of self-similar sets
- Recursive Real Numbers
- Type 2 recursion theory
This page was built for publication: Computability of Self-Similar Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238423)
