Chaos game

Last updated
Animated creation of a Sierpinski triangle using a chaos game method Sierpinski chaos animated.gif
Animated creation of a Sierpinski triangle using a chaos game method
The way the "chaos game" works is illustrated well when every path is accounted for. Sierpinski Chaos.gif
The way the "chaos game" works is illustrated well when every path is accounted for.

In mathematics, the term chaos game originally referred to a method of creating a fractal, using a polygon and an initial point selected at random inside it. [1] [2] The fractal is created by iteratively creating a sequence of points, starting with the initial random point, in which each point in the sequence is a given fraction of the distance between the previous point and one of the vertices of the polygon; the vertex is chosen at random in each iteration. Repeating this iterative process a large number of times, selecting the vertex at random on each iteration, and throwing out the first few points in the sequence, will often (but not always) produce a fractal shape. Using a regular triangle and the factor 1/2 will result in the Sierpinski triangle, while creating the proper arrangement with four points and a factor 1/2 will create a display of a "Sierpinski Tetrahedron", the three-dimensional analogue of the Sierpinski triangle. As the number of points is increased to a number N, the arrangement forms a corresponding (N-1)-dimensional Sierpinski Simplex.

Contents

The term has been generalized to refer to a method of generating the attractor, or the fixed point, of any iterated function system (IFS). Starting with any point x0, successive iterations are formed as xk+1 = fr(xk), where fr is a member of the given IFS randomly selected for each iteration. The iterations converge to the fixed point of the IFS. Whenever x0 belongs to the attractor of the IFS, all iterations xk stay inside the attractor and, with probability 1, form a dense set in the latter.

The "chaos game" method plots points in random order all over the attractor. This is in contrast to other methods of drawing fractals, which test each pixel on the screen to see whether it belongs to the fractal. The general shape of a fractal can be plotted quickly with the "chaos game" method, but it may be difficult to plot some areas of the fractal in detail.

With the aid of the "chaos game" a new fractal can be made and while making the new fractal some parameters can be obtained. These parameters are useful for applications of fractal theory such as classification and identification. [3] [4] The new fractal is self-similar to the original in some important features such as fractal dimension.

Optimal value of r for every regular polygon

Optimal value of r for every N-sided regular polygons, with N going from 5 to 20. R opt vs N.png
Optimal value of r for every N-sided regular polygons, with N going from 5 to 20.

At each iteration of the chaos game, the point xk+1 can be placed anywhere along the line connecting the point xk and the vertex of choice, v. Defining r as the ratio between the two distances d(xk,xk+1) and d(xk,v), it is possible to find the optimal value of r, i.e., ropt, for every N-sided regular polygon, that produces a fractal with optimal packing, i.e., the subscale polygons are in contact but do not overlap.

The value of ropt can be calculated as the ratio between the length of the side of the first subscale polygon and the side of the original polygon. This ratio can be calculated geometrically: [5]

In which a is calculated as:

Where θ is the internal angle of the polygon and n is the index of the most protruding vertex, counted starting from the base, i.e. where represents the integral part of the fraction.

Expansion of the chaos game for values of r greater than 1

While an optimally packed fractal appears only for a defined value of r, i.e., ropt, it is possible to play the chaos game using other values as well. If r>1 (the point xk+1 jumps at a greater distance than the distance between the point xk and the vertex v), the generated figure extends outside the initial polygon. [5] When r=2, the algorithm enters in a meta-stable state and generates quasi-symmetric figures. For values of r>2, the points are placed further and further from the center of the initial polygon at each iteration, the algorithm becomes unstable and no figure is generated.

Restricted chaos game

A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex. No fractal appears. V4 unrestrict.gif
A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex. No fractal appears.

If the chaos game is run with a square, no fractal appears and the interior of the square fills evenly with points. However, if restrictions are placed on the choice of vertices, fractals will appear in the square. For example, if the current vertex cannot be chosen in the next iteration, this fractal appears:


A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be the same as the previously chosen vertex. V4 ban1.gif
A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be the same as the previously chosen vertex.


If the current vertex cannot be one place away (anti-clockwise) from the previously chosen vertex, this fractal appears:


A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be 1 place away (anti-clockwise) from the previously chosen vertex. V4 ban1 inc1.gif
A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be 1 place away (anti-clockwise) from the previously chosen vertex.


If the point is prevented from landing on a particular region of the square, the shape of that region will be reproduced as a fractal in other and apparently unrestricted parts of the square.

Jumps other than 1/2

When the length of the jump towards a vertex or another point is not 1/2, the chaos game generates other fractals, some of them very well-known. For example, when the jump is 2/3 and the point can also jump towards the center of the square, the chaos game generates the Vicsek fractal:

A Vicsek fractal generated by the chaos game V4jump2 3 center.gif
A Vicsek fractal generated by the chaos game

When the jump is 2/3 and the point can also jump towards the midpoints of the four sides, the chaos game generates the Sierpinski carpet:

A Sierpinski carpet generated by the chaos game V4jump2 4 center.gif
A Sierpinski carpet generated by the chaos game

Chaos game used to represent sequences

Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=0.5) EU81043 1-r05 letters.png
Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=0.5)
Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=2) EU81043 1-r2 letters.png
Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=2)

With minor modifications to the game rules, it is possible to use the chaos game algorithm to represent any well-defined sequence, i.e., a sequence composed by the repetition of a limited number of distinct elements. In fact, for a sequence with a number N of distinct elements, it is possible to play the chaos game on an N-sided polygon, assigning each element to a vertex and playing the game choosing the vertices following the progression of the sequence (instead of choosing a random vertex). In this version of the game, the generated image is a unique representation of the sequence. This method was applied to the representation of genes (N=4, r=0.5) [6] [7] and proteins (N=20, r=0.863). [5] [8] Additionally, the representations of protein sequences was used to instruct ML models to predict protein features. [5] [9] The expansion of the chaos game using r=2 can be useful to magnify small mutations in the comparison between two (or more) sequences. [5]

See also

Related Research Articles

<span class="mw-page-title-main">Fractal</span> Infinitely detailed mathematical structure

In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illustrated in successive magnifications of the Mandelbrot set. This exhibition of similar patterns at increasingly smaller scales is called self-similarity, also known as expanding symmetry or unfolding symmetry; if this replication is exactly the same at every scale, as in the Menger sponge, the shape is called affine self-similar. Fractal geometry lies within the mathematical branch of measure theory.

<span class="mw-page-title-main">Sierpiński carpet</span> Plane fractal built from squares

The Sierpiński carpet is a plane fractal first described by Wacław Sierpiński in 1916. The carpet is a generalization of the Cantor set to two dimensions; another is Cantor dust.

<span class="mw-page-title-main">Sierpiński triangle</span> Fractal composed of triangles

The Sierpiński triangle, also called the Sierpiński gasket or Sierpiński sieve, is a fractal attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles. Originally constructed as a curve, this is one of the basic examples of self-similar sets—that is, it is a mathematically generated pattern that is reproducible at any magnification or reduction. It is named after the Polish mathematician Wacław Sierpiński, but appeared as a decorative pattern many centuries before the work of Sierpiński.

<span class="mw-page-title-main">Fractal art</span> Form of algorithmic art

Fractal art is a form of algorithmic art created by calculating fractal objects and representing the calculation results as still digital images, animations, and media. Fractal art developed from the mid-1980s onwards. It is a genre of computer art and digital art which are part of new media art. The mathematical beauty of fractals lies at the intersection of generative art and computer art. They combine to produce a type of abstract art.

<span class="mw-page-title-main">Julia set</span> Fractal sets in complex dynamics of mathematics

In the context of complex dynamics, a branch of mathematics, the Julia set and the Fatou set are two complementary sets defined from a function. Informally, the Fatou set of the function consists of values with the property that all nearby values behave similarly under repeated iteration of the function, and the Julia set consists of values such that an arbitrarily small perturbation can cause drastic changes in the sequence of iterated function values. Thus the behavior of the function on the Fatou set is "regular", while on the Julia set its behavior is "chaotic".

<span class="mw-page-title-main">Fractal compression</span> Compression method for digital images

Fractal compression is a lossy compression method for digital images, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image. Fractal algorithms convert these parts into mathematical data called "fractal codes" which are used to recreate the encoded image.

<span class="mw-page-title-main">Menger sponge</span> Three-dimensional fractal

In mathematics, the Menger sponge is a fractal curve. It is a three-dimensional generalization of the one-dimensional Cantor set and two-dimensional Sierpinski carpet. It was first described by Karl Menger in 1926, in his studies of the concept of topological dimension.

<span class="mw-page-title-main">24-cell</span> Regular object in four dimensional geometry

In four-dimensional geometry, the 24-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {3,4,3}. It is also called C24, or the icositetrachoron, octaplex (short for "octahedral complex"), icosatetrahedroid, octacube, hyper-diamond or polyoctahedron, being constructed of octahedral cells.

<span class="mw-page-title-main">Iterated function system</span>

In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. They were introduced in 1981.

<span class="mw-page-title-main">Sierpiński curve</span>

Sierpiński curves are a recursively defined sequence of continuous closed plane fractal curves discovered by Wacław Sierpiński, which in the limit completely fill the unit square: thus their limit curve, also called the Sierpiński curve, is an example of a space-filling curve.

In mathematics, the T-square is a two-dimensional fractal. It has a boundary of infinite length bounding a finite area. Its name comes from the drawing instrument known as a T-square.

<span class="mw-page-title-main">Euclidean tilings by convex regular polygons</span> Subdivision of the plane into polygons that are all regular

Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his Harmonices Mundi.

<span class="mw-page-title-main">Hexagonal tiling</span> Regular tiling of a two-dimensional space

In geometry, the hexagonal tiling or hexagonal tessellation is a regular tiling of the Euclidean plane, in which exactly three hexagons meet at each vertex. It has Schläfli symbol of {6,3} or t{3,6} .

<span class="mw-page-title-main">Apeirogon</span> Polygon with an infinite number of sides

In geometry, an apeirogon or infinite polygon is a polygon with an infinite number of sides. Apeirogons are the two-dimensional case of infinite polytopes. In some literature, the term "apeirogon" may refer only to the regular apeirogon, with an infinite dihedral group of symmetries.

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.

In geometry, a uniform tiling is a tessellation of the plane by regular polygon faces with the restriction of being vertex-transitive.

<span class="mw-page-title-main">Abelian sandpile model</span> Cellular automaton

The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

<span class="mw-page-title-main">Barnsley fern</span> Fractal which resembles a plant

The Barnsley fern is a fractal named after the British mathematician Michael Barnsley who first described it in his book Fractals Everywhere. He made it to resemble the black spleenwort, Asplenium adiantum-nigrum.

An n-flake, polyflake, or Sierpinski n-gon, is a fractal constructed starting from an n-gon. This n-gon is replaced by a flake of smaller n-gons, such that the scaled polygons are placed at the vertices, and sometimes in the center. This process is repeated recursively to result in the fractal. Typically, there is also the restriction that the n-gons must touch yet not overlap.

<span class="mw-page-title-main">Ulam–Warburton automaton</span>

The Ulam–Warburton cellular automaton (UWCA) is a 2-dimensional fractal pattern that grows on a regular grid of cells consisting of squares. Starting with one square initially ON and all others OFF, successive iterations are generated by turning ON all squares that share precisely one edge with an ON square. This is the von Neumann neighborhood. The automaton is named after the Polish-American mathematician and scientist Stanislaw Ulam and the Scottish engineer, inventor and amateur mathematician Mike Warburton.

References

  1. Weisstein, Eric W. "Chaos Game". MathWorld .
  2. Barnsley, Michael (1993). Fractals Everywhere. Morgan Kaufmann. ISBN   978-0-12-079061-6.
  3. Jampour, Mahdi; Yaghoobi, Mahdi; Ashourzadeh, Maryam; Soleimani, Adel (1 September 2010). "A new fast technique for fingerprint identification with fractal and chaos game theory". Fractals . 18 (3): 293–300. doi:10.1142/s0218348x10005020. ISSN   0218-348X via ResearchGate.
  4. Jampour, Mahdi; Javidi, Mohammad M.; Soleymani, Adel; Ashourzadeh, Maryam; Yaghoobi, Mahdi (2010). "A New Technique in saving Fingerprint with low volume by using Chaos Game and Fractal Theory". International Journal of Interactive Multimedia and Artificial Intelligence . 1 (3): 27. doi: 10.9781/ijimai.2010.135 . ISSN   1989-1660.
  5. 1 2 3 4 5 Arsiccio, Andrea; Stratta, Lorenzo; Menzen, Tim (2023-11-15). "Evaluating the chaos game representation of proteins for applications in machine learning models: prediction of antibody affinity and specificity as a case study". Journal of Molecular Modeling. 29 (12): 377. doi:10.1007/s00894-023-05777-0. ISSN   0948-5023.
  6. Jeffrey HJ (1990) "Chaos game representation of gene structure". Nucleic Acids Res 18(8):2163–2170. https://doi.org/10.1093/nar/18.8.2163
  7. Jeffrey, H. Joel (1992-01-01). "Chaos game visualization of sequences". Computers & Graphics. 16 (1): 25–33. doi:10.1016/0097-8493(92)90067-6. ISSN   0097-8493.
  8. Almeida, Jonas S.; Vinga, Susana (2009-03-31). "Biological sequences as pictures – a generic two dimensional solution for iterated maps". BMC Bioinformatics. 10 (1): 100. doi: 10.1186/1471-2105-10-100 . ISSN   1471-2105. PMC   2678093 . PMID   19335894.
  9. Zhou, Qian; Qi, Saibing; Ren, Cong (2021-03-01). "Gene essentiality prediction based on chaos game representation and spiking neural networks". Chaos, Solitons & Fractals. 144: 110649. doi:10.1016/j.chaos.2021.110649. ISSN   0960-0779.