[Graphics:Images/index_gr_1.gif] is recognizable

by giving an algorithm that accepts only two different IFSs

Definitions

Let denote Φ the finite set of matrices of an IFS.
    [Graphics:Images/index_gr_2.gif]
In general, the matrices are of the affine form
[Graphics:Images/index_gr_3.gif] where [Graphics:Images/index_gr_4.gif] with [Graphics:Images/index_gr_5.gif] and [Graphics:Images/index_gr_6.gif].
[Graphics:Images/index_gr_7.gif] is the dimension of [Graphics:Images/index_gr_8.gif] and [Graphics:Images/index_gr_9.gif] is the translation component of a affine matrix [Graphics:Images/index_gr_10.gif].

Let    [Graphics:Images/index_gr_11.gif]
and    [Graphics:Images/index_gr_12.gif].

Let [Graphics:Images/index_gr_13.gif] be the set of the identity matrix of dimension [Graphics:Images/index_gr_14.gif].
Then we can define the set of all products of the IFS [Graphics:Images/index_gr_15.gif] at iteration level [Graphics:Images/index_gr_16.gif]
    [Graphics:Images/index_gr_17.gif] recursively.
In words, we compute [Graphics:Images/index_gr_18.gif] the set of matrices of level [Graphics:Images/index_gr_19.gif] from [Graphics:Images/index_gr_20.gif] the set of matrices of level [Graphics:Images/index_gr_21.gif] by multiplying each matrix [Graphics:Images/index_gr_22.gif] with each [Graphics:Images/index_gr_23.gif] from the right.
Equivalently, [Graphics:Images/index_gr_24.gif].
Elements from [Graphics:Images/index_gr_25.gif] correspond to matrices [Graphics:Images/index_gr_26.gif] where [Graphics:Images/index_gr_27.gif]. [Graphics:Images/index_gr_28.gif] can be called a limit point.

Now we impose a last condition for an IFS, the manifold condition: We require an IFS to satisfy [Graphics:Images/index_gr_29.gif] and w.l.o.g. [Graphics:Images/index_gr_30.gif] such that [Graphics:Images/index_gr_31.gif] for any [Graphics:Images/index_gr_32.gif] ([Graphics:Images/index_gr_33.gif] for any [Graphics:Images/index_gr_34.gif]).
Note, that otherwise the IFS reduces to [Graphics:Images/index_gr_35.gif], i.e. the limit set [Graphics:Images/index_gr_36.gif] consists only of one element.

Let [Graphics:Images/index_gr_37.gif] and [Graphics:Images/index_gr_38.gif] denote the finite set of matrices of the two IFS, [Graphics:Images/index_gr_39.gif] and [Graphics:Images/index_gr_40.gif].

• Definition [Graphics:Images/index_gr_41.gif]: The IFSs [Graphics:Images/index_gr_42.gif] and [Graphics:Images/index_gr_43.gif] are not equivalent, iff there is an open interval [Graphics:Images/index_gr_44.gif] ([Graphics:Images/index_gr_45.gif] Borel-measure [Graphics:Images/index_gr_46.gif]) such that an infinite number of limit points [Graphics:Images/index_gr_47.gif]
    either built from elements of [Graphics:Images/index_gr_48.gif] are in [Graphics:Images/index_gr_49.gif] whereas no limit points from [Graphics:Images/index_gr_50.gif] are in [Graphics:Images/index_gr_51.gif],
    or built from elements of [Graphics:Images/index_gr_52.gif] are in [Graphics:Images/index_gr_53.gif] whereas no limit points from [Graphics:Images/index_gr_54.gif] are in [Graphics:Images/index_gr_55.gif].
Note, otherwise [Graphics:Images/index_gr_56.gif].

Comparision of two IFS with dimension d=1

Let Φ and Ψ denote the finite set of matrices of the two IFS, [Graphics:Images/index_gr_57.gif] and [Graphics:Images/index_gr_58.gif]. In general a matrix is of the form
[Graphics:Images/index_gr_59.gif] where [Graphics:Images/index_gr_60.gif] and [Graphics:Images/index_gr_61.gif].

Example: An IFS in 1D that converges to the cantor-set is given by [Graphics:Images/index_gr_62.gif] with
[Graphics:Images/index_gr_63.gif] and [Graphics:Images/index_gr_64.gif].

[Graphics:Images/index_gr_65.gif]


Let a matrix [Graphics:Images/index_gr_66.gif] correspond to the point with coordinates [Graphics:Images/index_gr_67.gif]. The process of taking all combinations of matrix products of our example is visualized obove. The cantor set is then the union of all "limit-points" on the [Graphics:Images/index_gr_68.gif]-axis.

Acording to the definitions above, [Graphics:Images/index_gr_69.gif] and [Graphics:Images/index_gr_70.gif] is the set of all products at level k of iteration. Note, to compute level [Graphics:Images/index_gr_71.gif], we multiply each [Graphics:Images/index_gr_72.gif] with each [Graphics:Images/index_gr_73.gif] from the right. The collection of all products form [Graphics:Images/index_gr_74.gif].

Let [Graphics:Images/index_gr_75.gif], and [Graphics:Images/index_gr_76.gif] with [Graphics:Images/index_gr_77.gif]. Then
    [Graphics:Images/index_gr_78.gif].

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 [Graphics:Images/index_gr_79.gif] more:

[Graphics:Images/index_gr_80.gif], 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 [Graphics:Images/index_gr_81.gif] is
    [Graphics:Images/index_gr_82.gif]
hence, "only" of magnitude [Graphics:Images/index_gr_83.gif].

In the following, we yield an upper bound for β and take advantage of making [Graphics:Images/index_gr_84.gif]  sufficiently small.

To yield an upper bound for the translative component β of all matrices of an IFS at the level [Graphics:Images/index_gr_85.gif], we get inspiration from
    [Graphics:Images/index_gr_86.gif]

and understand that in general, we yield the expression
    [Graphics:Images/index_gr_87.gif] for [Graphics:Images/index_gr_88.gif].

Since Φ contains a finite number of matrices
    [Graphics:Images/index_gr_89.gif] and
    [Graphics:Images/index_gr_90.gif] are well defined.
Note that still [Graphics:Images/index_gr_91.gif]. With these values we can bound [Graphics:Images/index_gr_92.gif]  [Graphics:Images/index_gr_93.gif] such that

    [Graphics:Images/index_gr_94.gif]

The sum is the geometric series and we can conclude, letting [Graphics:Images/index_gr_95.gif] -> ∞
    [Graphics:Images/index_gr_96.gif].

Hence, no product can be formed with translation part β with magnitude greater than [Graphics:Images/index_gr_97.gif].
In our example for the cantor set, we yield that [Graphics:Images/index_gr_98.gif]. This corresponds to the steepest possible slope in the figure.

We apply the previous result to consider obtainable limit points [Graphics:Images/index_gr_99.gif] from an element [Graphics:Images/index_gr_100.gif] at level k. It follows that [Graphics:Images/index_gr_101.gif]. [Graphics:Images/index_gr_102.gif] is refered to as the event horizon of [Graphics:Images/index_gr_103.gif] in [Graphics:Images/index_gr_104.gif].

Side note: In graphical terms one could say, that the event horizon [Graphics:Images/index_gr_105.gif] forms a "cone" with top [Graphics:Images/index_gr_106.gif], which is unioned with the mirror cone at [Graphics:Images/index_gr_107.gif]. 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 [Graphics:Images/index_gr_108.gif] for two IFSs [Graphics:Images/index_gr_109.gif] and [Graphics:Images/index_gr_110.gif]:
We compute the elements of [Graphics:Images/index_gr_111.gif] and [Graphics:Images/index_gr_112.gif] simultaneously for increasing levels [Graphics:Images/index_gr_113.gif]. At each level [Graphics:Images/index_gr_114.gif], we consider for all [Graphics:Images/index_gr_115.gif] the set [Graphics:Images/index_gr_116.gif], of which there are finitely many, with the union of all [Graphics:Images/index_gr_117.gif], defined for Ψ analogously, and conversly. We can stop if
    either    a)    [Graphics:Images/index_gr_118.gif] for some [Graphics:Images/index_gr_119.gif]
    or    b)    [Graphics:Images/index_gr_120.gif] for some [Graphics:Images/index_gr_121.gif].
Because a) and the manifold condition ⟹ ∃ [Graphics:Images/index_gr_122.gif] that generates infinitely many limit points, that lie separated from all limit points of Ψ. Similarly b).

• Lemma 1: Let [Graphics:Images/index_gr_123.gif] and Ψ be two IFSs. Algorithm 1 accepts input [Graphics:Images/index_gr_124.gif] iff [Graphics:Images/index_gr_125.gif].
Proof: [Graphics:Images/index_gr_126.gif] [Graphics:Images/index_gr_127.gif] are accepted [Graphics:Images/index_gr_128.gif] w.l.o.g. a) is satisfied, i.e. [Graphics:Images/index_gr_129.gif] such that [Graphics:Images/index_gr_130.gif] is disjoint from [Graphics:Images/index_gr_131.gif]. Yet [Graphics:Images/index_gr_132.gif] is closed in [Graphics:Images/index_gr_133.gif]. If we continue recurring [Graphics:Images/index_gr_134.gif] from [Graphics:Images/index_gr_135.gif] to some level [Graphics:Images/index_gr_136.gif], we yield a [Graphics:Images/index_gr_137.gif] with [Graphics:Images/index_gr_138.gif] with [Graphics:Images/index_gr_139.gif] due to the manifold condition. Hence, we can construct an open set in [Graphics:Images/index_gr_140.gif] containing [Graphics:Images/index_gr_141.gif] entirely and infinite number of limit points of [Graphics:Images/index_gr_142.gif] and none of [Graphics:Images/index_gr_143.gif].
[Graphics:Images/index_gr_144.gif] [Graphics:Images/index_gr_145.gif] with [Graphics:Images/index_gr_146.gif] open such that w.l.o.g. infinitely many input points of [Graphics:Images/index_gr_147.gif] lie in [Graphics:Images/index_gr_148.gif], but no limit points of [Graphics:Images/index_gr_149.gif] are in [Graphics:Images/index_gr_150.gif]. [Graphics:Images/index_gr_151.gif] such that [Graphics:Images/index_gr_152.gif] with [Graphics:Images/index_gr_153.gif]. This [Graphics:Images/index_gr_154.gif] will satisfy a). •

Multidimensional IFS

In order to extend this result to higher dimensional IFS, i.e. [Graphics:Images/index_gr_155.gif], treat [Graphics:Images/index_gr_156.gif] as a matrix and [Graphics:Images/index_gr_157.gif] 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]
[Graphics:Images/index_gr_159.gif]


Converted by Mathematica      December 13, 2004