Minglei Xu and Dr. Robert P. Burton, Computer Science
n-D fractals, where n> 4, have long been under scrutiny for their mathematical properties and artistic values. Multi-dimensional space filling curves, for instance, are a focus for contemporary topologists. Notable works in this area include the uses of quaternions, commutative hyper-complex calculus, and, most recently, doubling processes. However, all these discoveries have been limited to algebraic fractals such as the Mandelbrot set and the Julia sets. Algorithmic fractals are equally interesting since they serve as bridges connecting chaos theory to well studied formal language theory.1 2-D and 3-D algorithmic fractals are conventionally generated and analyzed using L-systems and iterated function systems (IFS). In this research, these techniques have been augmented and extended to study n-D algorithmic fractals.
Generation of 3-D Koch Curves
In order to understand how 3-D algorithmic fractals can be generalized to 4-D or even higher dimensional fractals, a process which is certainly difficult for humans, it is essential to understand how 2-D fractals can be generalized into 3-D. Consider a possible generalization of the classical construction of 2-D Koch curves into 3-D spaces (Fig. 1). Intuitively, instead of replacing the mid-one- third line segment with two line segments in the 2-D plane, replace it with eight segments into four directions, thereby expanding the three dimensions. Using formal languages, this generalization can be represented as an L-system: F F+F-F+F, where = {four possible rotations in four different directions in 3-D spaces}. In other words, F % (2-D rewrite rules of the same Lsystem), where % denotes concatenation.
Let ! be a set of 3 × 3 affine transformation matrices used by the IF S corresponding to the 2-D Koch curve L-system. Then !’ for the 3-D Koch curves can be computed by expanding ! to 4×4 matrices, and then left-multiplying by. Since 3-D and n-D translation, scaling, and rotation matrices are known, the formula, in a short hand, !’ = × ! is practical and convenient to extend to n-D spaces.
Generation of n-D Koch Curves and Other Algorithmic Fractals
Formal Analysis of Fractal Dimensions
For every n-D algorithmic fractal, the IFS theory predicts a fractal, or self-similarity, dimension D different than its Cartesian dimension n. Possibly, D will not be a whole number, and it can be computed as follows:
where a is the number of child line segments spawned from the parent line segment at each
application of the rewrite rules, and s is the contraction factor, i.e., the length of one child
line segment divided by the length of the parent line segment. For n-D Koch curves, where n 2,
a = 4n-1 and s = 1/3. Therefore,
Validation and Visualization
Software has been written to validate and visualize (in 2-D sections) these n-D algorithmic fractals. Due to space complexities, the implementation is limited to a 4-D Koch curve with only 100 pixels per dimension, which still takes as much as 100MB disk storage. Also, to eliminate numerical errors, the rewrite rules for the Koch curves have been modified as depicted in Fig. 2. Fig. 3 shows some of the experimental results. Clearly, common fractal features such as non-linearity and symmetry are present in these pictures.
References
- P. Prusinkiewicz and A. Lindermayer, The Algorithmic Beauty of plants, Springer-Verlag, New York, 1990.
FIG 1. Generation Scheme for 3-D Koch Curves.
FIG 2. Modified Koch Curves to Eliminate Numerical Errors.
FIG 3. A 4-D modified Koch Curve. A = xy-Cross Section at z = 0 and w = 0. B = xw-Cross
Section at y = ±9 and z = 0. C = xy-Cross Section at z = 0 and w = ±27.