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.
- True Shape Algorithm ( TSA)
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,
- complex plane
- region = union of the cell with the same label
- cell = rectangle in the complex plane
- directed graph
- cell graph that represents the cell mapping
- IA = Interval Arithmetic
- dyadic fraction
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 )
- 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. "
a quadtree decomposition of the complex plane
adaptive refinement = Subdivide each gray leaf cell into four new gray subcells
- Simple Cell Mapping (SCM)
- Generalized Cell Mapping (GCM)
- label propagation in graph
- C++ code by Marc Meidlinger, July-October 2019
- Haskell code by Claude
- CMlib is a library of cell mapping algorithms and utility functions and classes written in c++ by Gergely Gyebroszki
- "Images of Julia sets that you can trust" by Luiz-Henrique de Figueiredo, Diego Nehab, Jofge Stolfi, Joao Batista Oliveira- 2013
- "Rigorous bounds for polynomial Julia sets" by Luiz-Henrique de Figueiredo, Diego Nehab, Jofge Stolfi, Joao Batista Oliveira
- First Palis-Balzan Symposium on Dynamical Systems L. H. FIGUEIREDO - Images of Julia sets that you can trust
- Interval arithmetic in wikipedia
- Images of Julia sets that you can trust from Palis-Balzan Int Symposium
- flacco-tutorial gcm
- Images of Julia sets that you can trust by LUIZ HENRIQUE DE FIGUEIREDO. DIEGO NEHAB, JOAO BATISTA OLIVEIRA
- Images of Julia sets that you can trustby Luiz Henrique de Figueiredo oktobermat