by giving an algorithm that accepts only two different IFSs
Let denote Φ the finite set of matrices of an IFS.
In general, the matrices are of the affine form where
with
and
.
is the dimension of
and
is the translation component of a affine matrix
.
Let
and .
Let be the set of the identity matrix of dimension
.
Then we can define the set of all products of the IFS at iteration level
recursively.
In words, we compute the set of matrices of level
from
the set of matrices of level
by multiplying each matrix
with each
from the right.
Equivalently, .
Elements from correspond to matrices
where
.
can be called a limit point.
Now we impose a last condition for an IFS, the manifold condition: We require an IFS to satisfy and w.l.o.g.
such that
for any
(
for any
).
Note, that otherwise the IFS reduces to , i.e. the limit set
consists only of one element.
Let and
denote the finite set of matrices of the two IFS,
and
.
• Definition : The IFSs
and
are not equivalent, iff there is an open interval
(
Borel-measure
) such that an infinite number of limit points
either built from elements of are in
whereas no limit points from
are in
,
or built from elements of are in
whereas no limit points from
are in
.
Note, otherwise .
Let Φ and Ψ denote the finite set of matrices of the two IFS, and
. In general a matrix is of the form
where
and
.
Example: An IFS in 1D that converges to the cantor-set is given by with
and
.
Acording to the definitions above, and
is the set of all products at level k of iteration. Note, to compute level
, we multiply each
with each
from the right. The collection of all products form
.
Let , and
with
. Then
.
To understand the analysis for comparing two IFS of dimension 1, it is neccessary to understand the 2x2-matrix-multiplication for this special matrix format. In other words, we investigate the outcome more:
• , which means in the interpretation of the points in the plane, we are getting closer to the y-axis.
• the change of the translative component from level k to level is
hence, "only" of magnitude .
In the following, we yield an upper bound for β and take advantage of making sufficiently small.
To yield an upper bound for the translative component β of all matrices of an IFS at the level , we get inspiration from
and understand that in general, we yield the expression
for
.
Since Φ contains a finite number of matrices
and
are well defined.
Note that still . With these values we can bound
such that
The sum is the geometric series and we can conclude, letting -> ∞
.
Hence, no product can be formed with translation part β with magnitude greater than .
In our example for the cantor set, we yield that . This corresponds to the steepest possible slope in the figure.
We apply the previous result to consider obtainable limit points from an element
at level k. It follows that
.
is refered to as the event horizon of
in
.
Side note: In graphical terms one could say, that the event horizon forms a "cone" with top
, which is unioned with the mirror cone at
. I.e. we cannot yield matrices in greater levels which would correspond to points outside the previously described area.
• Algorithm 1: The previous considerations immediately give us an algorithm at hand, of which we prove below, that it accepts for two IFSs
and
:
We compute the elements of and
simultaneously for increasing levels
. At each level
, we consider for all
the set
, of which there are finitely many, with the union of all
, defined for Ψ analogously, and conversly. We can stop if
either a) for some
or b) for some
.
Because a) and the manifold condition ⟹ ∃ that generates infinitely many limit points, that lie separated from all limit points of Ψ. Similarly b).
• Lemma 1: Let and Ψ be two IFSs. Algorithm 1 accepts input
iff
.
Proof:
are accepted
w.l.o.g. a) is satisfied, i.e.
such that
is disjoint from
. Yet
is closed in
. If we continue recurring
from
to some level
, we yield a
with
with
due to the manifold condition. Hence, we can construct an open set in
containing
entirely and infinite number of limit points of
and none of
.
with
open such that w.l.o.g. infinitely many input points of
lie in
, but no limit points of
are in
.
such that
with
. This
will satisfy a). •
In order to extend this result to higher dimensional IFS, i.e. , treat
as a matrix and
as the translation vector in the previous computations. One can choose the 2-norm for matrices and vectors.
Remark:
![[Graphics:Images/index_gr_158.gif]](Images/index_gr_158.gif)