Visualization of the Chaos Game for non-hyperbolic
iterated function system
Pablo José Mavares Ferrer
Instituto Tecnológico El Pacífico
pmavares@tecnologicopacifico.edu.ec
https://orcid.org/0000-0001-7342-6262
Abstract
The chaos game is a random algorithm generally applied to contracting (hyperbolic) iterated
function system (IFS) which makes it possible to obtain the unique attractor of the dynamic
system. However, when applied to non-contractive IFS extremely interesting results can be
obtained that are not only important from a theoretical and application point of view, but can
also be part of a mathematical didactics that seeks to modernize teaching. In this sense, this
research present some results related to the application of the chaos game to non-contracting
IFS are presented.
Keywords: Chaos game, dynamic systems, iterated function system
Resumen
El juego del caos es un algoritmo aleatorio generalmente aplicado a sistemas de funciones
iteradas (IFS) contractivas (hiperbólicas), lo que hace posible obtener un único atractor del
sistema dinámico. Sin embargo, cuando se aplica a IFS no contractivos se pueden obtener
resultados extremadamente interesantes que no solo son importantes desde el punto de vista
teórico y de aplicación, sino que puede ser parte de la didáctica matemática que busque
modernizar la enseñanza. En este sentido, esta investigación presenta algunos resultados
relacionados con la aplicación del juego del caos a los IFS no contractuales.
Palabras clave: Juego del caos, sistemas dinámicos, sistema de funciones iteradas
Introduction
The chaos game is an algorithm that serves to create fractal figures (M. Barnsley, 1988, 2004,
2006; M. Barnsley & Vince, 2011). Traditionally it has been visualized for contractive or
contractive on average iterative function systems (IFS), such that the theorem of the
contractive mapping guarantees the existence of a single attractor (M. Barnsley, 2006;
Peitgen, Jürgens, & Saupe, 2004), one of the best-known cases is the Sierpinski triangle. A
great contribution to the generalization of the chaos game to non-contractive IFS was
proposed by Barnsley and Vince (2011) where it is exposed how the chaos game can be used
to obtain the attractor of general IFS if the system has a single attractor. However, in the
works that this document is aware of, no varied literature has been found related to the
visualization of the chaos game corresponding to non-contractive IFS, both in cases where a
single attractor is obtained and in which no.
Although theoretical progress has been made in the cases of non-hyperbolic IFS (M. Barnsley
& Vince, 2011; Díaz & Matias, 2018; La Torre & Mendivil, 2013) this paper do not seek to
present theoretical aspects that contribute to the works of these authors and theory in general,
but it is sought to show the figures that result from applying the chaos game, with special
emphasis on how functions and linear transformations associated with a non-hyperbolic IFS
can create beautiful and complex but not necessarily fractal figures.
The visualization is significant particularly in math teaching didactics, as it is important to
establish relations of what is being looking at and what it stated in a formal symbolic way
(Gatica & Ares, 2012). Even though, this investigation is not approached from an education
point of view but from a general way that seeks to encourage the interested in topics that are
non-typical in today math curriculum.
1. Hyperbolic IFS
First let's consider some fundamental definitions that are necessary to understand the
difference between a contractive and a non-contractive IFS.
Definition 1. An iterated function system or IFS consists of a finite sequence of
transformations fi : X X for i 1, 2, where
N 1 is an integer and
X, d
is a
complete metric space. An IFS is usually denoted by
F
X; f
1
, f
2
,
, f
N
.
An IFS with probabilities consist of and IFS and a sequence of probabilities p1 , p2 ,
positive real numbers such that
probability.
p
1
p
2
pN 1, thus each function is associated with a
Definition 2. A transformation
f
: X
X
in a metric space
X, d
is called contractive if the
scale factor s is less than one and equal or greater than zero, thus the distance associate to the
metric space is given by equation 1.
d
f
x
, f
y
s d
x, y
x, y X
(1)
Definition 3
. Let
X, d
a complete metric space. Let
f
1
,
f
2
,
be a finite sequence of
strictly contractive transformations fN : X X , for n 1, 2, . Then
F
X; f
1
, f
2
,
Theorem 1. Let
is called a strictly contractive IFS or a hyperbolic IFS.
f
: X
X
be a contractive application in a metric space
X, d
. Then
f
has exactly one single fixed point p f X and also for any point x X the sequence
f
n
x
:
n
1, 2, 3,
converges to pf . This can be expressed by equation 2.
lim f
n
n
x
p
, x X (2)
A full proof of theorem 1 is detailed in Barnsley (1995). Many visualizations of chaos game
according to eq. 2 can be reviewed in literature (Devaney, 2018; Fabre, 2011; Garrison, 2016;
Huisman, 2017; Piretzidis, 2020; Wang-Hoyer, 2020). However, this work shows what
,
f
N
p
N
,
f
N
, N
, f
N
f
k
k
happen when the conditions of this theorem are not fulfilled. Therefore, the difference is
reduced to the scaling factor such that s is greater than one, thus obtaining a non-hyperbolic
IFS. This change that seems insignificant makes a big difference in the behaviour of the
dynamic system.
Methodology
Be a set of points called from now vertices located in a circle of radius one and be any point
Pi the chaos game considered in this article is to move in the direction of any vertex (selected
with a p probability that for simplicity is equal for each vertex) according to a scaling factor
s in such a way to obtain a new point Pi1 , this is held theoretically infinite times; although is
constrain to around 107 iterations due to hardware restriction.
So, all the results shown were obtained by applying equation 3 following the proposed
methodology. For this a programming in MATLAB was used.
x y
x y 1
x
y x
y
T
(3)
i
1
i
1
i i
k
v
n v
n i i
Where
xi1 and
yi1 are the coordinates of the iteration i 1 ;
xi and yi are the coordinates of the iteration i ;
k is a factor such that
s
1
0,1
;
s
1
1,
this is a generalization of a hyperbolic IFS where
xvn and yvn are the coordinates of the n vertex randomly selected;
T is a rotation transformation.
Equation 3 can be modified and different results will be obtained, it is possible to add not only
rotations, but also translations, reflections and shears, that is, different transformations. This
means that the results shown below apply to all these cases in general.
Results
Although the dynamic system studied is not contractive, the points obtained from the
iterations can be delimited to a closed set or can quickly tend to infinity, thus having or not a
unique attractor. Hence, an interesting question to ask is the following: ¿from which scaling
factor value does the system quickly tend to infinity? To answer this question from a
geometric point of view consider figure 1 (i) where any two vertices ( v1 and v2 ) are shown at
a distance v between them, in addition there is a distance d to any point
P
i
x
i
,
y
i
. The
general idea is to find a scaling factor such that the maximum distance between the point of
the next iteration Pi1 and any vertex is less than or equal to the maximum distance
(Euclidean) between the point Pi and the vertices, this guarantees that successive iterations
are within a closed set of points. This can be written in an inequality form (4).
s
d v
d d v
(4)
Where
s is the scaling factor such that
s
1
;
k
v maximum distance between any two vertices;
d maximum distance between point 𝑃𝑖 and vertices;
By rearranging 4, we get and inequality in terms of s (5).
s 2d v , d 0 and s 0
d
v
The graph of this inequality with v 1 is shown in Figure 1 (ii), a simple intuitive
(5)
interpretation of this result can be explained as follows: since the scaling factor s is assumed
constant, for small values of d the distance between the points of the iterations and the
vertices will increase but the increase will be contained in the limit to infinity of the iterations
if the scaling factor is less than 2, otherwise the points will go away more and more from the
vertices and quickly diverge to infinity (recalling that this is an iterative process).
(i)
(ii)
Figure 1. (i) An iteration considering the case studied (ii) Graph of inequality 5.
Source: P. J. Mavares, 2020
The previous result is very simple; it enhances the understanding of chaotic dynamical
system, particularly the chaos game. Although this work does not intend to discuss in deep
about the contributions of the chaos game to math education, obtaining and interpreting
inequality 5 from the proposed question can be a small challenge to students since it could
improve the reasoning of application of inequalities beyond just the resolution of structured
exercises. To visualize the above, consider Figure 2 which shows the case for a scaling factor
of 1.25, thus s 1 and the functions are non-contractive; however it is noted that successive
iterations converge, including a fractal figure even in a non-hyperbolic IFS. On the other
hand, Figure 3 shows the behavior of the system for the singular case 𝑠 = 2. In this case the
system generates a set with a strong symmetry that grows as the iterations increase, that is, it
does not converge to a single attractor.
Henceforth the starting point is considered as
0, 0
.
(i)
(ii)
(iii)
Figure 2. Chaos game with s 5 4 and a 45 rotation. (i) 104 iterations (ii) 106 iterations (iii) 2 107 iterations.
Vertices are shown as red points.
Source: P. J. Mavares, 2020
(i)
(ii)
(iii)
(iv)
(v)
(vi)
Figure 3. Chaos game with s 2 and a 45 rotation and 3 vertices. (i) 2 102 iterations. (ii) 103 iterations. (iii) 104
iterations. (iv) 105 iterations. (v) 106 iterations. (vi) 107 iterations.
Source: P. J. Mavares, 2020
Therefore, a small change in the scaling factor ds such that s ds 2 will cause the points to
move away from the vertices very quickly, this can see in Figure 4 (ii). In addition, it is
v
remarkable that when d the vertices can be approximated to a single point, so the
points of each iteration will lie on an approximated straight line (it is important to mention
that visually it gives the impression of being a continuous line, but the behavior is discrete). It
is clear that linear transformations applied affect the resulting set, in Figure 4 an example is
presented with a rotation of 45 , and since 360 45 8 , eight uniformly separated sets of
points arranged in a straight line will be obtained around the origin (since the vertices are
fixed around it).
(i)
(ii)
Figure 4. (i) 107 iterations with 10 vertices, s 2 and a 45 rotation. (ii) 107 iterations with 10 vertices,
s 2.0000004 and a 45 rotation. It is clearly noticeable that a small change ds drastically affects the dynamic
system.
Source: P. J. Mavares, 2020
An interesting result is the in which there is a small rotation angle
1 , this will create a
large number of points around the origin, which seems to generate a curve around (however
the set of points is finite) resulting similar to a logarithmic spiral; therefore, in polar
coordinates when d
Where:
the dynamic system can be expressed by equation 6.
r
i
1
i
1
r
i
(
s
1)
i
(6)
ri is the radius and
i is the angle of point Pi in polar coordinates;
ri1 is the radius
i1 of point Pi1 in polar coordinates;
s is the scaling factor;
is the rotation angle;
Figure 5 presents a comparison between the result obtained from the chaos game and the
result obtained from equation 6, the form and behavior are similar, the differences are that
equation 6 only applies to d v .
v
(i)
(ii)
Figure 5. (i) shows the result after applying 106 iterations, with 10 vertices, a scaling factor of s 1 / 0.4999 and a
rotation angle
0.1 . In (ii) the result is shown after applying 106 iterations using the equation 6.
Source: P. J. Mavares, 2020
Unlike a hyperbolic IFS where it is guaranteed to have a single attractor regardless of the
sequence of vertices selected for the iterations, Figure 6 evidence that for a scaling factor
equal to two the set of points does depend on the order of selection of vertices (in each case
created randomly thanks to MATLAB’s rand function). In all cases, although the figures are
not fractal, they are extremely beautiful, so it is again evident that chaotic dynamic systems
can create extremely complex figures from very simple functions that without going into
details of theoretical aspects and of applications, by themselves they seem created by an artist.
Figure 6. 106 iterations with a rotation angle of 60 and four vertices with different sequence of vertices selection.
Source: P. J. Mavares, 2020
Like the case of a hyperbolic IFS, the points generate a figure that depends on the number of
vertices as shown in Figure 7 (when the scaling factor is equal to two). Of course, in this the
figures are not fractal, changing the transformations it is possible to have infinite different sets
of points.
n 3
n 4
n 5
n 6
n 7
n
Figure 7. 106 iterations with s 2 and a rotation of 80 with different number n of vertices.
Source: P. J. Mavares, 2020
Conclusions
The chaos game has traditionally been used to obtain fractal figures in hyperbolic IFS.
Despite this, its use for non-contracting systems is equally interesting, being able to generate
figures with high beauty and symmetry. The visualization of the chaos game for non-
hyperbolic IFS can be as striking as the presentation of the best-known fractal figures, which
can generate interest on the part of the students in seeking to understand the theoretical
foundations behind these dynamic systems, particularly it was visible that a small change in
the scaling factor generates an abrupt change in the behavior of the dynamic system, therefore
this serves as an intuition of what chaos is.
Dynamic systems have been interesting in recent years because they have hidden interesting
patterns related to various aspects including mathematics, medicine, biology and nature in
general. That is why it is recommended to investigate even more in non-hyperbolic systems,
since they can still hide patterns to be found.
References
Barnsley, M. (1988). Barnsley Fractals Everywhere. Academic Press, INC.
Barnsley, M. (2004). Ergodic theory, fractal tops and colour stealing. 1, 1–17.
Barnsley, M. (2006). Super Fractals. Cambridge University Press.
Barnsley, M. F. (1995). Fractals Everywhere. Morgan Kaufmann.
Barnsley, M., & Vince, A. (2011). The chaos game on a general iterated function system.
Ergodic Theory and Dynamical Systems, 31(4), 1073–1079.
https://doi.org/10.1017/S0143385710000428
Devaney, R. L. (2018). Discrete Dynamical Systems: A Pathway for Students to Become
Enchanted with Mathematics. In Teaching and Learning Discrete Mathematics
Worldwide: Curriculum and Research (pp. 137–144).
https://doi.org/10.1192/bjp.112.483.211-a
Díaz, L. J., & Matias, E. (2018). Non-hyperbolic Iterated Function Systems: semifractals and
the chaos game. (August). http://arxiv.org/abs/1808.10283
Fabre, C. (2011). Chaos Game 2D/3D. http://demonstrations.wolfram.com/ChaosGame2D3D/
Garrison, D. (2016). The Chaos Game.
https://la.mathworks.com/matlabcentral/fileexchange/55508-the-chaos-game
Gatica, S. N., & Ares, O. E. (2012). La importancia de la visualización en el aprendizaje de
conceptos matemáticos. Edmetic, 1(2), 88–107.
http://www.uco.es/revistas/index.php/edmetic/article/view/220
Huisman, S. (2017). The Chaos Game - Sierpinski triangles and beyond.
https://community.wolfram.com/groups/-/m/t/1025180
La Torre, D., & Mendivil, F. (2013). A Chaos game algorithm for generalized iterated
function systems. Applied Mathematics and Computation, 224, 238–249.
https://doi.org/10.1016/j.amc.2013.08.049
Peitgen, H.-O., Jürgens, H., & Saupe, D. (2004). Chaos and Fractals. In Mathematica.
https://doi.org/10.1016/B978-044450002-1/50063-1
Piretzidis, D. (2020). Chaos game simulator.
https://la.mathworks.com/matlabcentral/fileexchange/44908-chaos-game-simulator
