# fast algorithms for external angle computations

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?

• 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. – Claude Jul 26 '18 at 13:59