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

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 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:[1]

  • 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

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

algorithms

edit
  • 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 )[3]
  • 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)[4]

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[5][6]
  • "Rigorous bounds for polynomial Julia sets" by Luiz-Henrique de Figueiredo, Diego Nehab, Jofge Stolfi, Joao Batista Oliveira

Video

edit

references

edit
  1. fractalforums.org : determining-optimal-iterations-to-skip-with-series-approximation
  2. Interval arithmetic in wikipedia
  3. Images of Julia sets that you can trust from Palis-Balzan Int Symposium
  4. flacco-tutorial gcm
  5. Images of Julia sets that you can trust by LUIZ HENRIQUE DE FIGUEIREDO. DIEGO NEHAB, JOAO BATISTA OLIVEIRA
  6. Images of Julia sets that you can trustby Luiz Henrique de Figueiredo oktobermat