Presentation  

${defaultAlt}
 

Visualizing Space-Filling Curves with Fractals and Web Publishing

Snow dim animation

Space-Filling Curves

History

Discovered by Peano in 1890.

Graphically simpler example found by Hilbert, 1891.

Other examples due to E.H. Moore, Lebesgue, Osgood, Sierpinski, and Knopp.

Definition: A space-filling curve is a continuous function from an interval into real n-dimensional space whose image contains an n-dimensional disk (n at least 2).

Example: Hilbert's curve

Hilbert's curve Hilbert's curve

Hilbert's curve Hilbert's curve

Hilbert's curve Hilbert's curve

Fractals

History

"Discovered" by Cantor in 1883 - his "set" has dim~0.631

Other examples given by von Koch (snowflake curve) in 1905, Weierstrass (no-where differentiable curves)

Named by Mandelbrot in 1975

Definition(?): A set with non-integer dimension.

Definition: A self-similar set, formed of N pieces with linear stretching factor S, has similarity dimension D, where SD=N.

Examples:

Segment: S = 2, N = 2, D = 1

Square region: S = 2, N = 4, D = 2

Cube: S = 2, N = 8, D = 3

Cantor set: S = 3, N = 2, 3D=2, D=ln(2)/ln(3)

More Fractals - Iterated Function Systems

Developed by Wunderlich in 1954 and popularized by Barnsley in 1988, Iterated Function Systems provide a useful way to define self-similar fractals.

In the real line, the two functions that shrink by 1/3 toward 0 or 1 completely define the Cantor set. It's the only compact set closed under applying the two functions and taking the union. Also, starting with any compact set, repeatedly applying those two functions and unioning will give sets converging to the Cantor set.

In the plane, consider 4 functions shrinking by a factor of s toward each of the four corners of the unit square. For s=1/2, the "attractor" is the square region. For smaller s, we get a Cantor set as drawn below.

allca

Connecting Fractals and Space Filling Curves with IFS's

Consider unit square and four maps:

  • f0 and f3 shrink by s toward lower corners and flip over diagonal through corner
  • f1 and f2 shrink by s toward upper corners

Compare 2nd approx to Hilbert curve with result of applying maps to 1st approx.

Hilbert's curve Hilbert's curve

Fact 1: Starting with any curve from 0 to 1 (or any curve at all and throwing in connecting segments), with proper speed choice, this process will converge to the standard Hilbert curve.

Fact 2: Shrinking in the IFS procedure we get approximating curves (in the limit) of various dimensions.

Back to top