Fractals/Iterations in the complex plane/tsa

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

nameEdit

  • True Shape Algorithm ( TSA) 

theoryEdit

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 wordsEdit

  • 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

algorithmsEdit

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. "

decompositionEdit

a quadtree decomposition of the complex plane

refineEdit

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

cell mappingEdit

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

label propagationEdit

  • label propagation in graph

codeEdit

PeopleEdit

PapersEdit

  • "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

VideoEdit

referencesEdit

  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