Dr Rupert Rawnsley. June 2005.

I would
like to thank Dr John Hedley for reading and commenting on this work throughout
its evolution, Dr Luiz de Figueiredo
for taking time to comment on the previous
paper, and Dr Bill Walster for his encouragement
and enthusiasm.

The
application of interval arithmetic to the task of drawing the Mandelbrot set
was introduced in a previous
paper. The motivation for this work was not principally the production of
fractal images (although it's always nice to have some eye-candy), but to
explore the application of interval arithmetic to the simulation of a simple
chaotic systems.

It was
concluded that a moderate amount of further work could round off some of the
rough-edges in the initial approach. The algorithm used by Joãn
Batista Oliveira and Luiz
Henrique de Figueiredo
(described in their presentation "Images
of Julia sets that you can trust") to produce images from the, very
similar, Julia set was adapted to the Mandelbrot set. Their approach was
innovative because it allowed the fractal to be characterized by strict,
mathematically guaranteed, set membership. This scheme has been reproduced and
more thoroughly described in this paper and extended to the Mandelbrot set.

Dr de Figueiredo and Dr Walster have
been very generous with their comments about the previous paper, and it has not
been possible to do justice to the wide range of issues raised. The relevant
correspondence is available on request, but a publishable version would be a
whole paper in itself, and one that I do not feel qualified to edit.

A simple
application was developed for this paper that builds on the one from the
original paper, again in Microsoft C#.NET. The new application supports Mandelbrot
and Julia fractals using either single-point or interval arithmetic. The binary
files (for Windows 2000 and above) are available here, and the source code is also available for reference purposes. This
tool requires that you have the .NET framework installed on your machine (see http://support.microsoft.com/?kbid=316091).

The single
point version of the algorithm is standard and does not warrant explanation.

For the
interval algorithm, the Mandelbrot equation is applied iteratively to the
region of the complex plane, C, under investigation:

*Z*_{n}_{+1} = *Z*_{n}^{2} + *C*

Where *Z*_{0} is the interval [0, 0] + [0, 0]*i*.

The initial
value for *C* is the box describing the whole region of the complex plane
as follows:

*C* = [*x*_{min},
*x*_{max}] + [*y*_{min},
*y*_{max}]*i*

Where *x*
is the real component, and *y* the imaginary component, as shown in the
following figure:

The
horizontal and vertical midpoints (*x*_{mid} and *y*_{mid}) are bisected such that the midpoint falls
on the nearest pixel boundary:

The four
quarters are then tested for membership, and subdivided in the same way if
still indeterminate. This continues until the size of the region is exactly one
pixel, if this pixels membership still cannot be determined then it is marked
as "Indeterminate" (grey).

The
algorithm used to determine Mandelbrot set membership for every region, *C*,
is as follows:

1.
Seed
*Z* with [0, 0] + [0, 0]*i*.

2.
Seed
set *P* as empty.

3.
Apply
*Z* = *Z*^{2} + *C*.

4.
If
*Z* is inside any of the complex
intervals in *P* then label *C* as "definitely in" and
terminate.

5.
If
*Z* is completely outside the
magnitude-2 circle then label *C* as
"definitely out" and terminate.

6.
If
*Z* completely contains the magnitude-2
circle then label *C* as
"indeterminate" and terminate.

7.
Add
*Z* to *P*.

8.
Goto 3.

The
following diagrams illustrate the three termination conditions of the
algorithm, corresponding to the three possible states of set membership:

One
interesting difference between the interval algorithm and the single-point
algorithm is that there is no need for an iteration limit "bail-out".
The time complexity of the algorithm has not been derived, but in practice it
seems to terminate in several thousand iterations. This upper limit tends to
increase as the zoom level increases, which correlates with experience of the
single-point algorithm, where greater iteration limits are required to resolve
“deeper” features.

The
algorithm used for the Julia set was identical to that for the Mandelbrot
except that *C* is a constant and *Z* is seeded with the complex interval
bounding the region under investigation.

The
constant *C* characterizes the
particular Julia set under investigation (as in the single point algorithm),
but the interval components of *C* are
artificially widened by the smallest possible increment to eliminate the
possibility of introducing the sort of sampling noise intrinsic in the
single-point approach. In limited experiments, this modification made no
discernable difference to the output.

A small
number of results are presented here, but the reader is encouraged to download
the tool and explore the fractals for themselves.

The
following two figures are the single point Mandelbrot set (left) and the
interval Mandelbrot set (right). Clearly the two images differ significantly,
and the same features as were seen in the first paper are present, but the new
“definitely out” boundary (white/grey interface) is clearly present.

Pseudo-detail
can be seen if the traditional approach of coloring by termination iteration is
applied. In the following figures the termination iteration controls the
saturation of the color and the white and grey are replace with blue and red
respectively:

Here is the
single and interval versions of the San Marco Julia set (-1 + 0*i*)

The
following is a Julia (0.293333333333333 + -0.28*i*) that exhibits an interesting Moiré pattern:

Clearly the
conclusions of the previous paper still stand: that single point and interval
arithmetic approaches to fractal generation produce considerably different
results. Furthermore, the interval algorithm described in this paper offers
guarantees about set membership not offered by the previous implementation or
the single point approach.

It is quite
likely that a the size of the indeterminate regions can be reduced by more
sophisticated algorithms or greater precision, and any researcher looking to
apply interval arithmetic to chaotic systems may find this a useful starting
point or sounding board for new ideas.

We must
also entertain the possibility that no significant reduction can be made in the
areas of indeterminacy, and it might be that chaotic systems and interval
arithmetic are not comfortable bedfellows (even for such a simple system as the
Mandelbrot and Julia equations). However, this pessimism must be tempered by
two considerations:

1.
This
is a toy problem, and it is not possible to say if a high level of
indeterminacy would actually be a disadvantage in a real world application.
Perhaps the “interesting” solutions always fall into definitive categories, or
enough latitude exists to discard indeterminate solutions in favor of
determinate ones.

2.
The
single point approach intrinsically has these problems, they are just not
explicit. This is a common caveat when criticizing many interval approaches.