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]

  • True Shape Algorithm ( TSA) 

theory[edit]

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]

  • 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

algorithms[edit]

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]

a quadtree decomposition of the complex plane

refine[edit]

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

cell mapping[edit]

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

label propagation[edit]

  • label propagation in graph

code[edit]

People[edit]

Papers[edit]

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

references[edit]

  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