Interior iteration with less period pain

In a previous post I said a little bit about the field structure of the exterior of the Mandelbrot set.

I mentioned that field lines with rational angles (rational multiples of 2π radians) correspond to pinch points on the Mandelbrot set. The relationship is in fact much deeper than that. The angles of the field lines at a pinch point also tell you something about the interior components of the set on either side of the pinch.

As well as proving that the Mandelbrot set is "simply connected", Douady and Hubbard made the "MLC" conjecture that the Mandelbrot set is also "locally connected". This would mean that the Mandelbrot set can be formed by just pinching a disk and that it has no infinitely thin strings joining its components.

Points inside the Mandelbrot set either converge to a fixed point, or to a periodic cycle, or they iterate chaotically. Disk-like and cardioid-like components of the set whose points all converge to periodic cycles are called "hyperbolic components". The MLC conjecture implies that the set is made entirely of hyperbolic components, and therefore that points with chaotic evolutions are on the edge of the set.

Wikipedia has a nice picture of the main hyperbolic components of the Mandelbrot set labelled with their periodicities. Note that a bud's periodicity is a multiple of its parent bud's. You can also see that the periodicity of a bud off the main cardioid matches the number of antennae it has (counting the bud as well). The same periodicity also turns up in the angles of the field lines that land at the pinch point that joins the bulb to the cardioid.

Take for example the period-3 components. Their pinches have field lines whose angles are multiples of 1/7, i.e. 1 / (2³ - 1). When represented as binary fractions, the digits after the binary point repeat with period 3. 1/7 = 0.001001...; 2/7 = 0.010010...; 5/7 = 0.101101...; 6/7 = 0.110110...

Field lines corresponding to an irrational angles land at points on the Mandelbrot set with chaotic evolutions - their binary expansions do not repeat.

You can watch John Hubbard himself giving a brilliant 16 minute lecture about all this, which is much better than my excessively terse witterings. (He starts with 3.5 minutes on the Julia set for z := z² - 1 before moving on to the Mandelbrot set.)

There is a practical consequence to all this. When making pictures of the Mandelbrot set, if you can detect that a point has reached a cycle then you can stop iterating it early. You do not have to go all the way to your maximum iteration count so you can save time working on points in the interior of the set. Also, MLC suggests that whenever you have a significant interior area in your image, it will (within practical limits) be susceptible to cycle detection. (You can do more clever things with cycle detection like interior distance estimation, but I'm not worrying about that right now...)

Cycle detection can be pretty cheap - cheap enough to more than pay for itself in many Mandelbrot renderings. For example this image shows (in orange) which points were found to converge to cycles, and this saved about a third of the rendering time.

The way to implement it is to iterate two copies of z, a "tortoise" and a "hare", and keep two iteration counters. Start off with the tortoise's counter initialized to one and the hare's counter initialized to zero. Increment the hare's counter each time you iterate it, as usual. When the hare's iteration counter passes the tortoise's counter, iterate the tortoise once, and multiply the tortoise's counter by a number slightly greater than one. (I found a multiplier of 1.1 worked OK. Larger multipliers mean less work is done on the tortoise, but it requires more hare iterations to detect cycles.) Each time you iterate the tortoise check if it is the same as the hare, and if so you can immediately say the point is in the Mandelbrot set. (I cheated a bit and checked if the distance between tortoise and hare was less than 2^-52. A larger epsilon detects cycles earlier but may have false positives.)

I seem to remember one of my schoolmates baked knowledge of the Mandelbrot's primary cardioid into his program. Cycle detection is much a more elegant and comprehensive way of saving time :-)