Mandelbrot Set Efficiency

The traditional algorithm for drawing the Mandelbrot set is to loop over all pixels in a grid and estimate whether each is in the Mandelbrot set by iterating with the famous formula $$z_{n+1} = z_n^2 + x + y \cdot i$$

However, the fact that the Mandelbrot set has a continuous boundary hints at a more efficient method. In particular, it seems like it should be possible to compute the Mandelbrot set using a "painting" method:

function is_in_mandelbrot(pixel) {
    var real = 0;
    var imaginary = 0;
    for (var i = 0; i < 1000; ++i) {
        new_real = real * real - imaginary * imaginary + pixel.x;
        new_imaginary = 2 * real * imaginary + pixel.y;
        real = new_real;
        imaginary = new_imaginary;
        if (real * real + imaginary * imaginary > 0) return false;
    }
    return true;
}

var pixels_enqued = Set()
var pixels_to_check = Queue();
pixels_to_check.add([0, 0]);
pixels_enqued.add([0, 0]);
not_mandelbrot_set = Set()
while (!pixels_to_check.is_empty()) {
    pixel = pixels_to_check.pop();
    if (!is_in_mandelbrot(pixel)) {
        // not in mandelbrot set
        not_mandelbrot_set.add(pixel);
        if (pixels_enqued)
        if ({"x": pixel.x+1, "y": pixel.y} in pixels_enqued) {
	        pixels_to_check.add({"x": pixel.x+1, "y": pixel.y});
	        pixels_enqued.add({"x": pixel.x+1, "y": pixel.y})
	    }
	    if ({"x": pixel.x-1, "y": pixel.y} in pixels_enqued) {
	        pixels_to_check.add({"x": pixel.x-1, "y": pixel.y});
	        pixels_enqued.add({"x": pixel.x-1, "y": pixel.y});
	    }
	    if ({"x": pixel.x, "y": pixel.y+1} in pixels_enqued) {
	    	pixels_to_check.add({"x": pixel.x, "y": pixel.y+1});
	    	pixels_enqued.add({"x": pixel.x, "y": pixel.y+1});
	    }
	    if ({"x": pixel.x, "y": pixel.y-1} in pixels_enqued) {
	    	pixels_to_check.add({"x": pixel.x, "y": pixel.y-1});
	    	pixels_enqued.add({"x": pixel.x, "y": pixel.y-1});
	    }
    }
}

mandelbrot_set = Set();
for (pixel in grid) {
    if (!not_mandelbrot_set.contains(pixel))
        mandelbrot_set.add(pixel);
}

I'm not 100% sure this works, but I coded this in JavaScript and the resulting set looks like the Mandelbrot set, and is a couple order of magnitude faster. The big hurdle to proving that this approach converges to the true Mandelbrot set as pixel-size decreases is that you can imagine a cave of non-Mandelbrot set inside the Mandelbrot set. If this cave has an infinitesimally small "mouth", then the cave's interior will never be colored using this method, but will using the traditional method.

Like
Share
Login
Name: