test for membership in mandelbrot bulb of period n

Question

Is there a efficient test (formula or inequality) of whether a given point is in a bulb of period n? In other words, something other than running the iteration a lot of times to see if it converges to a period n cycle. I would like to apply such a method (if it exists) to writing some code.

Answer 1

A point is interior to a component of period $n$ if it is not interior to any component of lower period and:

$$\left|\frac{\partial}{\partial z} f_c^n(z_0)\right| \le 1 \text{, where} \\ f_c^n(z_0) = z_0$$

Given $n$, it's possible to find $z_0$ by Newton's method. Testing every $n$ from $1$ to maximum iteration limit is expensive, so an optimisation is to only test $n$ where $|z_n|$ reaches a new minimum.

More info in my blog post on practical interior distance rendering.

EDIT

If $c_1$ is in a period $n$ component, you can use Newton's method to find the nucleus of the component $c_0$ which satisfies $f_{c_0}^n(0) = 0$ (treating $f_c$ as a function of $c$, this time). Then you can compute a size estimate:

complex double size(complex double nucleus, int period) {
  complex double l = 1;
  complex double b = 1;
  complex double z = 0;
  for (int i = 1; i < period; ++i) {
    z = z * z + nucleus;
    l = 2 * z * l;
    b = b + 1 / l;
  }
  return 1 / (b * l * l);
}

For "circular" bulbs (almost all are not true circles), the magnitude of this size estimate (call it $d$) is approximately the diameter. Then for any $c_2$ you can do a simple circle inclusion test, say $k = \frac{2}{d}|c_2 - c_0| - 1$ then when $k < 0$ it's probably in the same bulb and when $k > 0$ it's probably not in the same bulb - $|k|$ gives a vague measure of certainty.

If you don't know the shape of the component, that's possible to find too, using the formula in Eq 5.8 in "On the shapes of elementary domains or why Mandelbrot Set is made from almost ideal circles?" by V.Dolotin, A.Morozov:

shape_t shape(complex double nucleus, int period) {
  complex double z = nucleus;
  complex double dc = 1;
  complex double dz = 1;
  complex double dcdc = 0;
  complex double dcdz = 0;
  for (int i = 1; i < period; ++i) {
    dcdc = 2 * (z * dcdc + dc * dc);
    dcdz = 2 * (z * dcdz + dc * dz);
    dc = 2 * z * dc + 1;
    dz = 2 * z * dz;
    z = z * z + nucleus;
  }
  complex double e = - (dcdc / (2 * dc) + dcdz / dz) / (dc * dz);
  if (cabs(e) < cabs(e - 1)) {
    return cardioid;
  } else {
    return circle;
  }
}

There might be a way to apply cardioid interior testing by using the complex result of the size estimate to transform $c_2$ to the corresponding point relative to the main period 1 cardioid - but the distortion of cardioids is quite apparent near cusps, so this probably wouldn't work very well.

The code in this answer is taken from my (pre-alpha) mandelbrot-numerics library: https://gitorious.org/mandelbrot http://code.mathr.co.uk/mandelbrot-numerics

Answer 2

Thanks for the answer. So it appears that one way or the other one needs to do iterations, in this case Newton's method. I will have to study your blog to understand this approach. In the equations you give, c is the point one is testing, and Zo is one of the points in the period n cycle, correct? What about an approach where if you know that a value C1 is in the period n bulb, there might an efficient (non-iterating) test for a nearby point C2 being in the same bulb. I recall from a Wikipedia article something about perturbation methods. This kind of sounds like what I am talking about, but I am not sure. I will have to study up on perturbation methods.