Orbit-Based Optimization

Robert P. Munafo, 2023 Jun 17.

"Orbit-Based Optimization" refers to a family of algorithmic techniques used in rendering the Mandelbrot Set and Julia Sets. The common principle is to exploit known properties of the iteration function and its "dynamics", with the goal of improving speed.

Many other methods are used to increase speed; see Speed Improvements for an overview of all of them.

Here some popular orbit-based algorithms. Each is described in greater detail under its own heading:

The Mandelbrot Set's mirror symmetry can be exploited in views that straddle the real axis, by plotting only the larger part of the view, then using a reflected copy of the appropriate portion of it to fill in the rest of the image.

Orbit Detection, in which a periodic attractive limit cycle is detected by explicit comparison of iterates. One or more previous iterates are retained in memory, and comparisons are made while the iteration is taking place.

Perturbation Methods iterate some points fully; these are called "key points" or "reference points"; and some type of interpolation or extrapolation is used to iterate most of the points. The cubic deltas method is one of these.

The Synchronous Orbit algorithm was the first published perturbation method. In it, a large grid of evenly-spaced points is iterated in parallel for a limited number of iterations before being split apart into separate points. Points are iterated individually as soon as they cease to travel together in a gridlike formation. The grid is tracked by following the iterates of key points (typically boundary points); non-key points are approximated by interpolation. "Control points" are also iterated and used to test the accuracy of the interpolation.

The Common Ancestors method (applicable only to Julia Sets), in which the dwells of many points can be calculated at once, utilizing the fact that any two points with a common iterate have all of their subsequent iterates in common (starting with the common iterate).

The Inverse Iteration method (also applicable only to Julia Sets) in which the iteration is performed in reverse, causing the boundary of the Julia Set to be attractive and thereby allowing a quick approximate picture of the boundary to be plotted.

revisions: 20040414 oldest on record; 20230617 add perturbation methods

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jun 18.

s.27