The computational complexity of some julia sets

ABSTRACT

Although numerous computer programs have been written to compute sets of points which claim to approximate Julia sets, no reliable high precision pictures of non-trivial Julia sets are currently known. Usually, no error estimates are added and even those algorithms which work reliably in theory, become unreliable in practice due to rounding errors and the use of fixed length floating point numbers.In this paper we prove the existence of polynomial time algorithms to approximate the Julia sets of complex functions f(z)=z²+c for |c|<1/4. We will give a strict computable error estimation w.r.t. the Hausdorff metric d_H which means that the set is recursive [10]. Although these and many more Julia sets J are proven to be recursive [12] and furthermore recursive compact subsets of the Euclidean plane are known to have a computable Turing machine time complexity [10], hardly anything is known about the computational complexity of non-trivial examples. The algorithms given in this paper compute the Julia sets locally in time O(k²• M(k)) (where M(k) is a time bound for multiplication of two k-bit integers). Roughly speaking, the local time complexity is the number of Turing machine steps to decide for a single point whether it belongs to a grid K_k⊆ (2^-k• Z)² such that d_H(K_k,J)≤ 2^-k.

REFERENCES

• 1: Michael Barnsley, Fractals everywhere, Academic Press Professional, Inc., San Diego, CA, 1988
• 2: R. L. Devaney. An introduction to chaotic dynamical systems. Addison-Wesley, Redwood City, 2nd edition, 1989.
• 3: R. Engelking. General Topology, volume~6 of Sigma series in pure mathematics. Heldermann, Berlin, 1989.
• 4: K. Falconer. Fractal Geometry. Mathematical Foundations and Applications. John Wiley & Sons, Chichester, New York, 1990.
• 5: H. Kamo, K. Kawamura, and I. Takeuti. Computational complexity of fractal sets. Real Analysis Exchange, 26(2):773--793, 2000/01.
• 6: J. Milnor. Dynamics in One Complex Variable. Vieweg, Braunschweig, 2nd edition, 2000.
• 7: H.-O. Peitgen, H. Jürgens, and D. Saupe. Fractals for the classroom, Part Two, Complex systems and Mandelbrot set. Springer, 1992.
• 8: H.-O. Peitgen and P. H. Richter. The beauty of fractals. Images of complex dynamical systems. Springer, Berlin, 1986.
• 9: D. Saupe, Efficient computation of Julia sets and their fractal dimension, Physica D, v.28 n.3, p.358-370, Oct. 1987 [doi>10.1016/0167-2789(87)90024-8]
• 10: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 11: K. Weihrauch. Computational complexity on computable metric spaces. Mathematical Logic Quarterly, 49(1):3--21, 2003.
• 12: Ning Zhong, Recursively enumerable subsets of Rq in two computing models: Blum-Shub-Smale machine and Turing machine, Theoretical Computer Science, v.197 n.1-2, p.79-94, May 15, 1998 [doi>10.1016/S0304-3975(97)00008-X]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
computational complexity, julia sets