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

• complex plane
• region = union of the cell with the same label
• cell = rectangle in the complex plane
• tree
• 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

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

# 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