< Fractals < Iterations in the complex plane

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
    • quadtree
  • graph
    • directed graph
    • cell graph that represents the cell mapping
  • IA = Interval Arithmetic[1]
  • 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 )[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

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

label propagation

  • label propagation in graph

code

People

Papers

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

references

  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
This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.