Is there a more efficient equation for the Mandelbrot lemniscates?

Question

A common coloring algorithm for the Mandelbrot Set is the escape time algorithm, which produces solid bands of color around the boundary of the set. These bands are bounded by a group of polynomial lemniscates of the form

$$x_n^2 + y_n^2 = r^2$$

Where $$x_n = x_{n-1}^2 − y_{n-1}^2 + x,$$ $$y_n = 2 x_{n-1} y_{n-1} + y,$$ $$x_0 = x,$$ $$y_0 = y,$$ And $r$ is the escape threshold (usually two, but other values can be used).

This family of curves starts with the circle $x^2 + y^2 = 4$, then the Cassini oval $(x^2 − y^2 + x)^2 + (2 x y + y)^2 = 4$, then the curve $((((x^2 − y^2 + x))^2 − ((2 x y + y))^2 + x))^2 + ((2(x^2 − y^2 + x) (2 x y + y) + y))^2 = 4$, and they get exponentially more complicated as you go on. As $n$ increases, the curves converge to the boundary of the Mandelbrot Set.

Working with this implicit form is extremely unwieldy, and plotting them is inefficient. Is there a better way to represent these curves? Say, a polar equation, or a complex function, or a set of parametric equations? I'd like a way to graph the curves that doesn't require such cumbersome expressions.

Answer 1

It's much more natural to use complex numbers. Regarding efficiency, complex iteration of $z \to z^2 + c$ gives a degree $2^{n-1}$ polynomial in $c$ in $O(n)$ work. I don't know if it's possible to do better than that: starting from a pre-expanded polynomial will be $O(2^n)$ work which is exponentially worse.

Suppose $c = x + i y$, $f_c(z) = z^2 + c$, $f_c^{\circ (n+1)}(z) = f_c^{\circ n}(f_c(z))$. Then $\frac{d}{dc} f_c^{\circ(n+1)}(z) = 2 f_c^{\circ n}(z) \frac{d}{dc} f_c^{\circ n}(z) + 1$. These can be calculated together in one inner loop (being careful not to overwrite old values that are still needed).

Now you can use Newton's root finding method to solve the implicit form $f_c^{\circ n}(0) = r e^{2 \pi i \theta} = t$ by $c_{m+1} = c_{m} - \frac{f_{c_m}^{\circ n}(0) - t}{\frac{d}{dc}f_{c_m}^{\circ n}(0)}$. Use the previous $c$ as initial guess for next $\theta$. The increment in $\theta$ needs to be smaller than about $\frac{1}{4}$ for the algorithm to be stable. Note that $\theta$ (measured in turns) wraps around the unit circle $2^{n-1}$ times before $c$ gets back to its starting point.

This approach is inspired by An algorithm to draw external rays of the Mandelbrot set by Tomoki Kawahira.

Compare with binary decomposition colouring (here with $r = 25$) (this particular image is rendered implicitly as a function from pixel coordinates to pixel colour, with edge detection of iteration bands $n$ as well as regions where $\Im f_c^{\circ n}(0) > 0$, where $n$ is the first iteration where $|f_c^{\circ n}(0)| > r$):

Answer 2

If you do not want use equations for drawing lemniscates you can use

• numerical methods tracing drawing equipotential curves
• edge detection for drawing boundaries of level sets ( LCM)