3
$\begingroup$

Two related problems related to the complex quadratic polynomial $f_c(z) = z^2 + c$ and Mandelbrot and/or Julia sets:

  1. find an external angle $\theta_c$ for a complex point $c$

  2. find a complex point $c_\theta$ for an external angle $\theta$

Currently I can do both of these by tracing external rays (outwards for 1, inwards for 2), but it is asymptotically too slow to be practical: $O(n^2)$ where $n$ is the sum of the preperiod and period of the external angle.

I implemented Wolf Jung's Spider Algorithm with a Path (in the appendix; for finding $c_\theta$), it seems to be $O(n^2)$, and with worse constant factors (possibly even asymptotically worse?) compared to ray tracing as it needs full precision right from the start ($O(n)$ bits) and does complex square roots - ray tracing does only arithmetic and needs only enough precision to resolve the steps between ray points (which I think increases roughly linearly for the section of the ray that I'm interested in: just close enough that Newton's method can find $c_\theta$), spider path needs enough precision to resolve the starting points on the unit circle.

Are there better algorithms? What is the asymptotic cost of the original Spider Algorithm, for example? Homotopy methods using differential equations seem to find all $O(2^n)$ roots in $O(n 2^n)$ time, could they be adapted to find 1 specific root in less than $O(n^2)$ time? Would perhaps the representation of external angles as angled internal addresses be relevant here?

$\endgroup$
1
$\begingroup$

This is more of a comment than a real answer, but it's too long for a comment:

Since you raise the question of practical computations, a long time ago I computed a small "database" of points on the Mandelbrot set, available here, containing a few tens of thousands of boundary points with rational external angles of small denominators, as well as, for points which are component roots, the corresponding component center, all being computed with machine accuracy. (I never did anything with this database except from putting it online; I didn't really publicize it, and it didn't receive any attention of any sort.)

This may not be what interests you, because it only concerns points with small preperiod and period, and I don't think the algorithms were particularly intelligent, but if you want I can make the code available. (Sadly, I've forgotten all about what this is about, so I can't really explain how any of it works, but there are a few comments. From what I can see, I seem to trace the external rays approximately to a certain point, and then use Newton's method to find a periodic point with the appropriate structure — this, of course, depends crucially on the fact that the preperiod and period are small.) Even if you don't find the code interesting, the result (linked above) might be worth looking at, if you need to check whatever better algorithm you find.

(The format of the database is itself a bit cryptic, I'm not sure what the last column means, but the first few columns are obviously the rational external angle expressed in turns, the real and imaginary part of the point, and whether the point is a Misiurewicz point, component root or component center; the last column probably has something to do with the preperiod and period.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the lines with @ in your last column indicate internal angle (in turns) of the root relative to the parent component. I made a similar database once mathr.co.uk/mandelbrot/feature-database.csv.bz2 . My strategy for periodic points (and roots, not included in the CSV) was: trace external ray until close enough to parent cardioid, then Newton's method to center, then trace internal ray(s) to child components. I didn't explore Misiurewicz points much. The trouble is that tracing an external ray to depth $N$ is $O(N^2)$, and the required $N$ may be related ~linearly to period. $\endgroup$ – Claude Jul 26 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.