Fractal Peano curves

Journal of Geometry Vol. 34 (1989)

0047-2468/89/020127-1251.50+0.20/0 (c) 1989 Birkhguser Verlag, Basel

FRACTAL PEANO CURVES

Peter R. Massopust

We show that the theory of iterated function systems (i.f.s.'s) can be used to construct and geometrically describe Peano curves. We present this point of view by exhibiting i.f.s.'s whose attractors are the graphs of some well-known Peano curves.

1. INTRODUCTION In 1890, Peano [14] showed that it is possible to map the unit interval I

continuously onto a

compact subset X of R 2. The existence of such a continuous vector-valued function f: I - - X came as a surprise and it showed that continuity in the component functions of f is not enough to ensure bijectivity. Later, Hilbert [8] replaced the purely arithmetic def'miton of f by a more descriptive geometric construction of graph(f). Other constructive methods for such functions (see for instance [8]) followed his example and at the beginning of this century Knopp [10] showed that all these different functions, which were called Peano or space-filling curves (more precisely, a Peano curve is the graph of f), could be obtain by a simple geometric construction. Examples of different types of Peano curves appeared over the years in the mathematical literature (see for instance [8], [12] and [13]), all of which exhibited a certain

self-similarity underlying their geometric construction.

Last year, H. Sagan [15] wrote an article about Lebesgue's and Schoenberg's space filling curve and their approximating polygons (approximating polygons were first introduced in [ 15] and are the polygonal paths through the midpoints of a sequence of squares that is defined by the geometric construction of the Peano curve). These two Peano curves and their approximating polygons seemed not to be generated by an obvious underlying geometric method. In this article we will show that the theory of iterated function systems is the right framework for Peano curves. We will see that Peano curves are the attractors of iterated function systems and that approximating polygons naturally arise from the images of an interval under iteration thus explaining their self-simAlarity.

128

Ymssopust

2. D E F I N I T I O N S A N D P R E L I M I N A R I E S In this section we review briefly iterated function system theory and give some necessao~ definitions. Let X be a compact subset of R 2 (in what follows this compact subset will usually be the unit square [0, 1] x [0, 1]) and let F = {fi: i = I ...... N}, N e 1~{ 1 }, be a collection of continuous functions fi: X - - X. Then the pair F x = CA, F ) is called an iterated function system ({iLs.): I f in addition all fl are contractive, i.e. 3 s ~ [0, 1) V i = 1 ..... N, V x, y ~ X: I fi(x) - fi(Y) ~ < < s I x - y I (I 9 I denotes the metric on X), then Fx is called a hyperbolic i.f.s. (h.i,f.s.). Every h.i.Ls, possesses a unique compact attractor A = A ( F x ) which is invariant under the setvalued map F: K(X) - - KCX), FOS) = ~J fi(E) (here K(X) denotes the set of all non-empty compact subsets of X). The attractor A has in general non-integer dimension. Such a set is called a

fractal. A can be constructed as follows: Let {Pi: i = 1..... N} be a set of nonzero probabilities, i.e. Pi ~ (0, 1) and ~ Pi = 1. Choose any x 0 a X. F X defines a time-discrete dynamical system if one generates successive states of the system by the rule that if x n is the state of Fx at time t = n then the state xn+ 1 at time t = n + 1 is given by xn.1 = fi(xn) with probability Pn. The sequence {xn} converges then to A with probability one and A equals the set u cl{xm: m >_ n), It can be shown that A is independent of x 0 and that the set-valued map F is contractive if F i s contractive which implies that Fn(E) - - A in the Hausdofff metric, VE ~ K(X) (F n = F , ..., F n times). For a more general definition of an i.f.s, and more details we refer the reader to [1]. W e call two i.f.s.'s Fx and F'x equivalent and write For =_F'x iff A ( F x ) - A ( F ~ ) . Recall that a map f ~ C(X), where C(X) denotes the set of all continuous functions on X, is a

similitude or a similarity map if f(x) = s R(x) + t, where s e R0+, R(x) an orthogonal transformation and t a translation vector. Now let us assume that all f i e Fx are similitudes. Furthermore assume that {xj a X: j = 0, 1 ..... N} is a collection of distinct points with the property that i) I x j + l - x j l < IXN-X01 V j = 0 ..... N ii)

the closed polygon 17 joining the points {xj} is simple

iii)

x0 = fl(x0),

iv)

S open set G c X such that u fig C G and f i g n fjG = 0 V i # j

XN = fN(xN) and fi.l(x0) = fi(xN) = xi V i = 1 ..... N

The last condition is called the open set condition and was first introduced by Hutchinson [9]. Conditions very similar to the ones above were also considered in [12]. Under the assumptions i) iv) above F x is a h.i.f.s.

Massopust

129

Associated with an i.f.s, is a code spaceK2. It is given by g~ = 1"I {vn ={1 ..... N}: n e N} and arises as follows: The forward gajectory or forward orbit of a point x a X under F x is the set O , = {x, f(o(x) ..... fo)~ ... 9 fc0(x).... } where ok e { 1..... N}, V k e N. Hence if 0) = (0)1 ... o k ... ) e s'2 then 0) determines an orbit for each x ~ X. The closure of the o - l i m i t set of these orbits is then the attractor A. But this implies that 'ga e A there exists exactly one 0) e ~ such that a =

lira k--,- ~

fc~ (x) )

with ~0(k) = (mk ... ml) and fo>(k)= fo~" ... | fco 9 It is easy to show that this limit exists and is independent of x. Thus we constructed a surjection ~ : f2 - - A which with the Fr~chet metric on ~ is also continuous. Now let I = [0, 1], let y e I and suppose that [Yl .-. Yk -..] denotes the N-ary expansion of y. Define the right-shift operator (r+ : ~ - - f2 by a+(0)1 02 "'" 0)k "") = (0)1+1 O2+1 "'" % + 1

.,.)

Then one easily proves P R O P O S I T I O N 1. The m a p h: I--, K2 defined by h(y = [Yl ... Yk ...]) = ~r+ [y, .,. Yk ...] iS a homeomorphism. W e can use this homeomorhism to define a map ~): I - - A by setting ~(y) = ( ~ 9 h)(y) g y ~ I. Since ~ is a continuous surjection, together with conditions i) - iv) this imphes that } is a continuous function from I to A. W e furthermore have that {(j/N, xj): j = 0 ..... N} C graph(13) = G C R2 x R. G is the attractor o f the h.i.f.s. F x where ~ = {~: X ~ X: i = 1..... N} with

fi(x,y) =

V i = 1. . . . . N fi(x)

Note that projx G = A(Fx). But we can say even more: T H E O R E M 1. I-1D(G) = HD(A(Fx)), where l i D denotes the Hausdorff-Besicovitch dimension o f G. HD(G) is the unique positive solution o f X s i HD(a) = I with si = L i p ( f i ) Vi = I ..... IV. For proofs we refer the reader to [1], [2], [5] and [9]. W e can use i.fis, theory to construct fractal function& i.e. functions whose graph is a fractal set. LetX~Q=[0,1]x[0,1]andletY={(xj,

yj) e Q : 0 = x 0 < . . . < X N = l , j = 0

..... N } b e a

given set of interpolation points. Let fi e F be such that fi(x, y) = (~.i(x), •i(x, y)), Vi = 1 ..... N,

130

~ssopust

where ~Li:[0, 1] ~ [xi.1, xi] is a homeomorphism with ~.i(x0) = xi_I and

~i(XN) =

Xi ~

=

1,

.... N, and ~:i(x, y): [0, 1] x R - - R a continuous map with ~q(x, .) contractive, ~i(', Y) Lipschitz, Ki(x0, Y0) = Yld and Ki(XN, YN) = Yi, 'v'i = 1..... N. The maps fi are then uniquely determined by Y together with a set of parameters 0 '~ I e i ~< 1, Vi, called the vertical scaling factors. A(FX) is the graph of a continuous and in general nowhere differentiable function q~: [0, 1] - - X containing T. Henceforth we will only consider maps fi = (%i, ~i) which are affine. The illustration below shows how the attractor A is obtained.

X

7

(•

(xi.~, J~-,) Illustration 1

If Y is such that YN = 0, x i - xi. 1 = N -1 and e i = b (0 < b < 1) 'r q~(t) = E bk Y(Nkt) k~0

then we can write ~p as

where ?(t) = F ([0, 1])

The sums B

r (t) = E bk 7(Nkt) k=O

n~N

may be cailed the n-th polygonal approximations to (p. The interested reader is referred to ElL [3], [5], [7] and [12] for a more detailed introduction to fractal functions. Let us remark that if the points {xj } are not linearly ordered then we obtain a frac~' curve instead of a fractal function. D E F I N I T I O N . / f the attractor o f an i.f.s, is the graph o f a continuous fractal curve with positive two-dimensional Jordan content, then we call A a two-dimensional Peano or space-tilting curve.

Massopust

131

REMARKS: a) Let p: [0, 1] --,- X be the Peano mapping. We will identify p with its graph A and refer to p as the fractal Peano curve. b) Although the dimension of A is an integer, we call p a fractal Peano curve since its construction indicates fractal properties.

3. GENERATION OF FRACTAL PEANO CURVES In this section we will see how some of the more well-known Peano curves can quite easily be obtained from i.Ls. theory. Let us first took at Hilbert's construction of a Peano curve. We will use the notation and terminology developped in section 2. Let X = Q and let Y = {(0, .25), (.25, .25), (.25, .75), (.75, .75)}. Define an i.f.s. F X by

1[;1 Notice that the fi satisfy conditions i) - iv) in section 2. and that Fx is hyperbolic. The attractor A is the graph of a continuous function p: L ~ X where L = [0, 1]. The image of L under F , called the generator of the Peano curve, is depicted in illustration 2o Iterating L m-times yields the m-th order approximating polygon Hm (as defined in [15] and [17]) for the Hilbert curve. The following illustration 3 shows II m for m = 6. Since all the fi are similitudes with s i = 0.5, i = 1..... 4, the formula for HD(A) in theorem 1 yields HD(A) = 2, as expected. One can interpret A = graph(p) as the projection of a fractal function /3: L ~ R 2 onto X, where ~3is generated by

~(x, y, z) =

lazi1] [

fi (x' Y)

Vi = 1..... 4

132

Ymssopust

and for which HD(graph(/5)) = HD(graph(p)) = 2.

,1)

(0,0)

N.g~C~gaS~_g~Npsg~

Illustration 2

Illustration 3

Let us remark that the generator of the Hilbert curve has two additional "legs" as compared to the one considered in [8], [151 or [17]. Their presence assures that the images of L under F are connected. Following the idea of constructing Peano curves using i.f.s, theory, one can qmte easily write down the generators and the resulting maps for all the Peano curves considered in [17] (one has to change the generators slightly so that their images are connected). Here are a few examples:

(0,0)

(1,0)

Illustration 4

Illustration 5

([171, p. 5)

([171, p. 9)

"Triangular" (Pt) and "square" (Ps) Peano curves can also be generated as follows: Pt:

fi(x'Y) = 7

_.1.i-1

1,,y,

+ ~

i = 1,2

Massopust

!33

Ps: ft(x'Y)

[ 111

1 0 g 1

1 0

x y

f2(x' y)

~ [ol

1 "2"

1

y

(see also [5]). The generators are given in illustration 6.

!

Q

Pt

Ps illustration 6

All these Peano curves are generated by similitudes and thus can be interpreted as being the projections of iso-dimensional fractal functions onto X. More interesting is the construction of Schoenberg's space-filling curve (see [15] and [16]). p: L --* X = 2Q (here aQ = [0, a] x [0, cq, c~> 0) is given by p(t) = if(t), g(t)) where f ( t ) = kE> t 71 7(3Zk-2t)

and

g(t) = E

1 ~/(3=klt)

kel7

with "r R/2Z -.- R/2Z defined by i ~t) =

0 < t < 1/3 1/3 ~ t < 2/3 2/3 ~ t < 1

t- 1

~,(t) = v(-O

We can write f and g as 1 f(t) = "~m~0 (~22)2m'Y(32mt) t ?(32re'It) g(t)

__1 2; ~/~ k ~ 1

134

Massopust

from which it follows that f and g are "parts" of a fractal function h: L ~ R h(t) = 2 f(t) + ~ g ( t )

=

7,00,;

T(3mt)

generated by the i.f.s. Fx with Y = {(0, 0), (1/3, 0), (2/3, 1), (1, 1), (4/3, 1), (5/3, 0), (2, 0)} and

fl (x' Y) =

-I

f2(x' y) =

47

~x,y~_-

Y

+

0

1-ff 0

f3 ( x ' y ) =

1

x

-1

y

x

2 +

+

-1~

-f4(x' y) =

0

x

{1|

-

I:1 l

f~,,~= ~

,~

§ ~-

0

Illustration 7 below shows how p(t) is constructed from f(t) and g(t). The m-th approximating polygon can then be obtained from the m-th poIygonai approximation for f and g via the above construction: fm(tq,m) = ~"

?(3Zkt) k=l ]

whemt m

1

q,m

=--q 3m

q = 0 , 1 ..... 3 m -1

2k-i

Note that the tq.m which yield the vertices (fm(tq,m), gm(tq,n0) of the m-th approximating polygon are the images of [0, 2] under the h.i.f.s. ALl [0, 1], A = {~,i: [0, 2] - - [0, 2]: i = 1 ..... 6}, ~,i(x) = 1/3 (x + i - 1), Vi = 1 ..... 6, naturally associated with the construction of the fractal function h.

Massopust

135

C~,f(O)

Illustration 7 Lebesgue's space-filling curve is constructed as follows: Let C be the classical middle-thirds Cantor set and let t r C. Then t can be written as E2mn t =n>l 3n

where o}n~ {0,1}

Vn~N

Let 13: C ~ C and & C ~ C be continuous surjecfions with

Y,

I~(t) = ..., n~1

2f~

~(t) = n ~ l

and

202n 3n

3n

Then f: [0, 1] ~ R and g: [0, 1] ~ R are continuous fractal functions if def'med by f(t)

=

E n > 1

On 2n

~

V t ~ 13C,

g(t) =

E

ton 2n

~

Vt 9 ~C

and for t ~ [0, 1] - pC and t ~ [0, 1] - ~C inductively by 1

f(t)=~

and g ( t ) = - 3 t + l

1

for~- < t <

2

and continued in this manner on the remaining intervals. Lebesgue's space-filling curve is given by p(t) = if(t), g(t)). The m-th approximating polygon I-1m o f p for odd m and even m is the image o f I = [0, 1/2] under iteration of the set-valued maps I~: K(X) -- K(X) and CJ: K(X) -- K(X):

3

~ ( 1 ) = F(i~nq(I)) ~ ~

= 1 Lj( ~ q ( 1 ) )

Vm r N

with F(I) = u {fi(I): i = 1..... 4} where fi maps I homeomorphically onto (1/2I) x {0}, (1/2I) • { t/2}, (1/2I + 1/2) • {0} and (1/2I + 1/2) • { 1/2} respectively, and where Lj(I) is the Iine segment between the initial point of fj+l(I) and the terminal point of fj(I).

136

Massopus~

~(I')=O(I')uk.J3j=1 Lj(I') cjm(I')

r=Ix{O}L~Ix{I/2}w{(x,y):2x+2y =~,~

3

= G(Gm'I(I')) ~ L.)j=1 Lj(Gm-t(I'))

Vme N

with O(I') = u{gi(I'): i = 1..... 4} where gi maps I' homeomorphicaily onto 1/2r, 112I' -.- (0, 1/2), 1/21' + (1/2, 0) and I/2I' + (1/2, 1/2) respectively. Lj now applied to r is defined as above. Obviously A(~') = A ( F ) and since Lip(fi) = 112 for all i = 1..... 4 we have that HD(A) = 2, as expected. In illustration 8 we constructed m-th approximating polygons for Lebesgue's spacetilling curve for m = 6 (left) and m = 7 (right) (see also [11]).

~0, 0 (0.0)

Illustration 8 Finally let us remark that Knopp's construction (see [10]) is yet another application of i.Ls. theory: We start with a triangle A = A(A,B,C) c R 2 with base AB = 1. We may also assume that A = (0, 0). Choose a number O E [0, 1) and map A affinely onto the subtriangles ~o = A0(A,D,C) and &~ = AI(E,B,C ) with l E)E I = O. Now repeat this process with A0 and At by choosing a new a) for each subtriangle (see also the illustration below). Let fl(O): A - - Lx0 and f2(O): A - -

A 1

denote the maps for this process. Let us remark that

although we use only two maps at every iteration, these maps are different because of the different O. At the n-th step we obtain an n-chain of triangles which we can enumerate dyadically by Ao...00, A0...01..... A1...10 and At...lp This sequence of triangles is shown to converge to a set A C R 2 which is a continuous and nowhere differentiable Jordan curve provided that the dimensions of atl triangles converge to zero and that their angles remain bounded away from zero as n ~ +oo

/~,~

f 2(0,)

j/~. _.

Illustration 9

Massopust

137

If we use the code space f2 = { I, 2} r'r for this i.f.s, then we see that the index d 1 d 2 ... d n .... d~. = 0 or t, of each triangle is related to co ~ D by co = o+ (d 1 d 2 ... d n ...). The parametric representation of the points z(t) e A is then a direct consequence of the existence of the continuous surjection @: ~ ~ A (see section 2). The details are given in Knopp [101. If we choose ~ = 0, then the above construction yields the Peano curve Pe REMARK. In 1982 Dekking [6] generalized the notion of a self-similar set as def'med by Mandelbrot ("The fractalgeometry of nature", Freeman 1982). He calls these generalized sets recurrent sets. Dekking's recurrent sets and his more general construction of fractals (compared to what we have developped in this paper) can also be used to describe fractal Peano curves. But there is an obvious relation between Dekking's recurrent sets and a new, more general class of i.f.s.'s, namely recurrent i.s explicitly discussed,

We refer the interested reader to [4] where these connections are

REFERENCES [ 1]

BAR_NSLEY, M.F.: Fractal functions and interpolation, Constructive Approximation, (1986)

i2]

BARNSLEY, M. F. and DEMKO, S.: Iterated function systems and the global construction of fractals, Proc. Roy. Soc. Lond., Ser. A, ~ (1985) 243 - 275.

~3]

BARNSLEY, M. F. and HARRINGTON, A.: The calcuclus of fractal interpolation functions (1985), Georgia Tech preprint

[4]

BARNSLEY, M.F., ELTON, J. and HARDIN, D.P.: Recurrent iterated function systems (1986), Georgia Tech preprint

[5]

BARNSLEY, M.F., ELTON, J., HARDIN, D. P. and MASSOPUST, P.R.: Hidden variable fractal interpolation functions, Georgia Tech preprint (1986).

[6]

DEKKING, F.M.: Recurrent sets, Adv. in Math. 4_4.(1982), 78 - 104

[7]

HARDIN, D. P. and MASSOPUST, P.R.: The capacity for a class of fractal functions, Commun. Math. Phys., 1.0.$. (1986) 455 - 460

[8]

HILBERT, D.: Ueber die stetige Abbildung einer Linie auf ein Flaechenstueck, Math. Ann., ~ (1891) 459 - 460.

[9]

HUTCHINSON, J.: Fractals and self-similarity, Indiana Univ. J. Math., 2LQ (1981) 731 - 747.

[10]

KNOPP, K.: Einheitliche Erzeugung und Darstellung der Kurven yon Peano, Osgood und Koch, Arch. Math. Phys., 2_fi (1917)103- 115.

[11]

LEBESGUE, H.: Leqons sur l'intEgration et larecherche des fonctions primitives, Gauthier-Villars, Paris, 1904, 44 - 45.

[12]

MASSOPUST, P.R.: Ph.D. thesis, Georgia Institute of Technology, 1986.

[13]

MASSOPUST, P.R.: Dynamical systems, fractal functions and dimension, 1987 (to appear in Proceedings of Topology)

138

Massopust

[14]

PEANO, G.: Sur une courbe qui remplit route une aire plane, Math. Ann., ~ 157- 160.

[16]

SAGAN; H.: Approximating polygons for Lebesgues and Schoenberg's ~pace filling curves, Amer. Math. Monthly (1986) 361 - 368.

[16]

SCHOENBERG, I. J,: The Peano curve of Lebesgue, Bull. Amer. Math. Soc., 44 (1938) 519. WUNDERLICH, W.: Ueber Peano Kurven, Elem. Math., 2__8(1973)1- 10.

[17]

LaGrange College LaGrange, GA 30240 U.S.A. (Eingegangen am 26. Oktober i 9 8 7 )

(1890)