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

# name

* True Shape Algorithm ( TSA)

# theory

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 classified 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,
Image that is 100% guaranteed correct:
* white pixels are guaranteed to contain no interior or boundary points
* black pixels are guaranteed to contain only interior points
* red pixels have not been able to be decided at the current resolution (they might contain both interior or boindary and exterior points).
Unfortunately in practice the images have a lot of red pixels. It means that this algorithm is for proving that images are mathemathically correct. Point-sampling method is for creating images. If one sees that image is not smooth ( boundaries of components are smooth curves) then takes a bigger resolution ( subpixel accuracy) to get proper = smooth image. If one take good point sampled image, then TSA algorithm will not find a wrong pixel in it.

# key words

* 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
* dyadic fraction : working with exactly double-representable numbers by using a near dyadic fraction

# algorithms

* goal of the algorithm is mathematical correctness of the image
* the price is slow and not beatiful images. TSA is very slow and not suitable for creating images with aesthetic appearance.
* algorithm is designed for for Julia sets
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. "

## decomposition

a quadtree decomposition of the complex plane

## refine

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

## cell mapping

* Simple Cell Mapping (SCM)
* Generalized Cell Mapping (GCM)

## label propagation

* label propagation in graph

# code

* 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

# People

* Luiz Henrique de Figueiredo

# Papers

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

# Video

* First Palis-Balzan Symposium on Dynamical Systems L. H. FIGUEIREDO - Images of Julia sets that you can trust

# references

* ↑ fractalforums.org : determining-optimal-iterations-to-skip-with-series-approximation
* ↑ 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
* fractalforums : trustworthy-2d3d-julia-set-source-code
* Trustworthy fractals by Claude Heiland-Allen
* fractalforums.org : julia-sets-true-shape-and-escape-time