An iterated function system is a list of contractive functions on a metric space. They are used in the study of fractal geometry to construct self-similar sets. More recently, the concept of an iterated function system with overlaps has appeared in the research literature. Google scholar lists quite a few such articles.

Could someone explain this new concept - what is an iterated function systems with overlaps?


1 Answer 1


In short

An IFS with overlaps, is an IFS that does not satisfy the open set condition.

Some details

First, an iterated function system is simply a list of contractive functions $\{f_i\}_{i=1}^m$ on a metric space. Often, the metric space is $\mathbb R^n$ and the functions are assumed to be be similarities, so that $$\left|f_i(x) - f_i(y)\right| = r_i\left|x-y\right|$$ for all $x,y$, and $i$.

If the metric space is complete, then it is well known that there is a unique, non-empty, compact set $E$ such that $$E = \bigcup_{i=1}^m f_i(E).$$ The set $E$ is called the attractor of the IFS and, when the functions are similarities, it is called self-similar.

In the computation of dimension, it is convenient to limit overlap. In the simplest case, we might assume that the union is disjoint. It turns out that this condition can be relaxed somewhat to something like "just touching". The technical formulation of this just touching condition is called the open set condition, which asserts that there is an open set $U$ such that $$U \supset \bigcup_{i=1}^m f_i(U),$$ with this union disjoint. Assuming the open set condition, the dimension of a self-similar set is easy to compute - it's the unique value of $s$ such that $$\sum_{i=1}^m r_i^s = 1,$$ where the $r_i$s are the contraction ratios of the $f_i$s. If the contraction ratios are all the same, say $r_i=r$ for all $i$, then this simplifies to the well known formula $$\operatorname{dim}(E) = \frac{\log m}{\log r}.$$

As an example consider the well known Sierpinski triangle:

enter image description here

This set consists of $3$ copies scaled by the factor $1/2$. The interior of the initial triangle shown on the left above can be used to establish the open set condition for this set. The dimension is of the limit, as approximated on the right, is $\log(3)/\log(2)\approx1.58496$.

Now consider the following modification obtained by adding one triangle:

enter image description here

This set consists of four copies of itself scaled by the factor $1/2$, but the copies overlap. If the open set condition were satisfied, then we could show that the dimension is 2, though it certainly doesn't look that the dimension should be two. As it turns out, the dimension is $$\frac{\log(2+\sqrt{2})}{\log{2}} \approx 1.77155.$$

Computations for the dimension of these types of sets is fairly technical. You can find details in some of the papers listed here. Search for the key words "overlap" or "finite-type".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.