Partial Homework Solutions

HW #1

1. See the text (pg.148).

2. See the text (pg.79).

3. See the text (pg.81).

4. Note that 7 of the 27 sub-cubes are removed, and that the scaling is 1/(1/3). The dimension is log(20)/log(3).

5. Consider Color Plates 2, 4 following pg.176 of your text. These physical objects are curve-like (topological dimension 1), as are the four classical fractals (the outline in the case of the island) but attempt to nearly fill space or the plane. The language of fractals provides a way to discuss such physical objects.

HW #2

1. See the text (pg.215).

2. See the text (pg.215).

3. For the Hausdorff dimension, the open sets U (see pg.217) may be taken to have arbitrarily small diameter (though not zero, as they are open) and so the Hausdorff measure is always a countable sum of arbitrarily small values and hence the infimum is zero for all s; so, s=0 is the dimension. For the box-counting dimension, choose boxes (intervals) U of size delta where delta<1/2 and find k such that 1/delta lies between k(k-1) and k(k+1). Then each U covers at most one of {1,1/2,...,1/k}. Now apply the limiting definition of the box-counting dimension.

4. See the text (Color Plates following pg.176). The physical significance typically is space-filling structure; the dimension is a measure of success w.r.t. that goal. The scale is generally a few orders of magnitude in either direction. They are statistically self-similar, which is a reflection of how such shapes arise in nature.

5. Taking fractal dimension greater than topological dimension as the definition includes all objects which have an unexpected dimensionality, but includes objects which are simply squares, etc., if one disregards their genesis; it considers how the curve got there, not just its final geometry. Hausdorff dimension is the measure which best coincides with a mathematical notion of dimension but is hard to compute; box-counting is needed in practice.

HW #3

1. The first is obvious; (.011111...) in base 2 may be summed as a geometric series. A rational point is (.010101...,.101010...) and an irrational point is (.101001000100001...,.010110111011110...).

2. The first time it gives three points, and similarly.

3. A typical ellipse has eight straight line segment sides, not necessarily of equal length. Circles are a special case.

4. Symmetry and positive definiteness follow from the fact that |x| is a metric on R. For the triangle inequality, we must show that d(x,y)=<d(x,z)+d(z,y) for all x,y,z; that is, max{|x1-y1|,|x2-y2|}=<max{|x1-z1|,|x2-z2|}+max{|z1-y1|,|z2-y2|}. This follows by writing d(x,y) as max{|x1-z1+z1-y1|,|x2-z2+z2-y2|} and using the triangle inequality for the absolute value to break up the two components.

5. For sin(x)=x we have only x=0; for cos(x)=x, iteration gives a value of approximately .739. The tangent function has infinitely many fixed points.

HW #4

1. a.) You should see the computed values begin to differ. This is due to differences in the precison.

b. You should see the computed values begin to differ. This is due to slight differences in the implementation of computer arithmetic.

2. The Koch curve is not empty (for example, the endpoints of the initiator are in it). It is closed in R2 since its topological dimension is 1 and it contains its endpoints. It's clearly bounded, and so is in H(R2). The Koch snowflake is the filled-in and so the fact that its boundary, there Koch curves, is closed, shows that it is in R2.

3. From the epsilon-dilation definition, this is approximately 7.36 (the distance from (.5,.5) on S to (5,5) plus 1).

4. From the epsilon-dilation definition, this is 1/(2(1+sqrt(2)) by dilating into the inner (missing) triangle.

5. From the epsilon-dilation definition, this is 1/6; since l2 does not vary based on where in the plane distances are measured, the distance would not change.

HW #5

1. Take, say, (.020202...) and (.022222...) in base three and note that w1 looks like a shift map on such sequences.

2. Similar to HW #3, Question 4.

3. Both w1 and w2 map [0,1] into a proper subset of itself and have derivative 1/3. Their fixed points are 0 and 1, respectively. The Hutchinson map is one-to-two on R so it cannot be compared to w1 and w2 there. By the result on pg.270-271 of the text, W has contractivity factor 1/3 also. By the Contraction Mapping Theorem, W has a fixed point (namely, the Cantor set).

4. This requires eight maps; w1 has matrix [1/3 0;0 1/3] and no shift, and the others are shifts of this. It is not a contraction mapping on R2 because W is one-to-eight in R2 and hence is not a transformation there.

5. The only possibility which makes intuitive sense and respects the triangle inequality is d(x,{})=infinity if x is in H(X).

HW #6

1. Modify the program cantor.m on the main course web page.

2. Modify the program sier.m on the main course web page.

3. Modify the program sier.m on the main course web page.

4. See HW #5, Question 4.

5. See HW #5, Question 4.

HW #7

1. See the program sierrand.m on the main course web page.

2. See the program sierrand.m on the main course web page

3. Modify the program sierrand.m on the main course web page

4. Advantages include the incredible compression rates achievable in principle plus the fact that the decoding proceeds in a natural way (vague image, then sharper, then sharper). Disadvantages include most notably the difficulty of finding an IFS (long encoding time) and the need for some self-similarity in the image for good compression; decoding can also be slow.

5. No, det(A) is not s.

HW #8

1. There are many ways to do this; one is to use A=[.5 0;0 .5] to shrink the rectangle to the lower quadrant in w1, then shift this for w2, w3, and w4.

2. See pg.365-6 of the text.

3. Pick a point and iterate.

4. Pick a point and iterate.

5. Some exhibit a form of self-similiarity but more to the point there are stable fixed and periodic structures, and semi-stable features like gliders.

HW #9

1. See Homework #7, Problem #4.

2. An example would be A=[.5 0;0 .5] (r1=.5) in map 1 and 2, translated, and A=[1.2 0;0 1.2] (r3=1.2) in map 3, if p1=.4, p2=.4, p3=.2. Then s=.5957. The attractor shows the stretching due to map 3.

3. Let A be the attractor. Then w1(z0)=z0 implies that if z0 is in S then z0 is in W(S), so the forward orbit of S under W contains z0 for each finite stage and hence (by compactness) so does the limit set A; that is, z0 is in A. But then w2(A) contains w2(z0); as w2(A) is contained in A; w2(z0) is in A.

4. a. Perturb the parameters in the Barnsley fern.

b. Choose a leaf and use the Collage Theorem.

5. In each case an initial set is subjected to the same type of transformation at each stage, but for the IFS the result is independent of the limit set, while for the initiator-generator it is not. A random IFS has the same limit as the deterministic IFS and is merely another way of computing it; a random Koch curve (say) is different from the deterministic case.

HW #10

1. Quadtree is simple but the triangular method can hide from the eye certain flaws. See pg.915-917 of the text.

2. Choose a tree-like image and apply the Collage Theorem.

3. The maps are similarities with contractivity factors .5, .5, .4, .5. The dimension is found from the formula on pg.272 of the text. Yes, it is just-touching so this is the self-similarity dimension.

4. DLAs form into a fractal by aggregration. Percolation builds as a natural fractal and at some point a critical value is reached.

5. a. Use a line segment and the random midpoint displacement method.

b. Start from a triangle or other polygon.

HW #11

1. Choose a (finite) range of energies and integrate 1/A to find the constant of proportionality. Plot c/A.

2. The g>1 case would be pock-marked with many more small craters.

3. There are many ways to do this. Set a unit (e.g., length of the boid). Set a rate at which changes are implemented (say, 1/4 unit per time step). A separation rule might be that if a boid gets too close to another, defined as closer than two units, it moves away (along the line connecting their centers of gravity) at its rate; if it is too close to two or more, a weighted average may be taken for the direction and possibly distance. Simialrly for alignment and cohesion.

4. For a square it is 4; it is not the same for all rectangles. For an equilateral triangle it is 6/3^(1/4); it is not the same for all triangles.

5. Detail at all levels can be good for realism but can also be too much detail (may need smoothing). Can be slow to generate but gives good results easily. Can store main components of terrain and add detail on-the-fly.

HW #12

1. A typical point wanders about the unit interval without repeating, but on the computer all points go to zero. This can be seen by writing the initial point in binary and noting that this is a shift map; all points with terminating expansions tend to zero.

2. The Binet formula tends to zero, but the recurrence relation explodes due to magnification of round-off error.

3. No, low values reliably follow high values.

4. The fixed points are at 0 and (a-1)/a, by solving f(x)=x.

5. Goes to the fixed point through a=3, then is period 4 at a=3.5, then wanders chaotically or diverges to negative infinity.