Fractals/Iterations in the complex plane/tsa

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Algorithm for computing images of polynomial Julia sets with mathemathical guarantees against sampling artifacts and rounding errors in floating points arithmethic.

name[edit | edit source]

  • True Shape Algorithm ( TSA) 

theory[edit | edit source]

algorithm computes a decomposition of the complex plane into three regions:

  • a white region, which is contained in exterior of Julia set
  • a black region, which is contained in the interior of Julia set
  • a gray region, which cannot be clasified as white or gray. It is a region which contains julia set J

It gives adaptive approximation of the Julia set. Spatial resolution limited by available memory.

K is contained in the escape circle of radius R = max(|c|, 2) centered at the origin,

key words[edit | edit source]

  • complex plane
    • region = union of the cell with the same label
    • cell = rectangle in the complex plane
  • tree
    • quadtree
  • graph
    • directed graph
    • cell graph that represents the cell mapping
  • IA = Interval Arithmetic[1]
  • dyadic fraction : working with exactly double-representable numbers by using a near dyadic fraction

algorithms[edit | edit source]

algorithm avoids :

  • point sampling ( 1-pixel aproximation): what happens between samples ?
  • function iteration in the escape-time algorithm ( do not use it)
  • Floating-point rounding errors ( squaring needs double digits )[2]
  • partial orbits ( program cannot run forever)

Main features of the algorithm:

  • "cell mapping to reliably classify entire rectangles " in the complex plane, not just a finite sample of points
  • "it handles orbits by using color propagation in graphs induced by cell mapping" = "tracks the fate of complex orbit by inspecting the directed graph induced by cell mapping"
  • "The numbers processed by the algorithm are dyadic fractions that are restricted in range and precision and the algorithm uses error-free fixed-point arithmetic whose precision depends only on the spatial resolution of the image. "

decomposition[edit | edit source]

a quadtree decomposition of the complex plane

refine[edit | edit source]

adaptive refinement = Subdivide each gray leaf cell into four new gray subcells

cell mapping[edit | edit source]

  • Simple Cell Mapping (SCM)
  • Generalized Cell Mapping (GCM)[3]

label propagation[edit | edit source]

  • label propagation in graph

code[edit | edit source]

People[edit | edit source]

Papers[edit | edit source]

  • "Images of Julia sets that you can trust" by Luiz-Henrique de Figueiredo, Diego Nehab, Jofge Stolfi, Joao Batista Oliveira- 2013[4][5]
  • "Rigorous bounds for polynomial Julia sets" by Luiz-Henrique de Figueiredo, Diego Nehab, Jofge Stolfi, Joao Batista Oliveira

Video[edit | edit source]

references[edit | edit source]

  1. Interval arithmetic in wikipedia
  2. Images of Julia sets that you can trust from Palis-Balzan Int Symposium
  3. flacco-tutorial gcm
  4. Images of Julia sets that you can trust by LUIZ HENRIQUE DE FIGUEIREDO. DIEGO NEHAB, JOAO BATISTA OLIVEIRA
  5. Images of Julia sets that you can trustby Luiz Henrique de Figueiredo oktobermat