# Hausdorff Dimension

• November 1st 2009, 04:55 AM
Media_Man
Hausdorff Dimension
Hello all. I am looking at branching binary trees in $\mathbb{R}^n$. Consider such a tree in which each branch is exactly twice the length of its two "child" branches. This can be defined iteratively as a self-similar fractal. I am trying to apply Hausdorff's rule of dimension represented by $N=L^D$, where N is the number of "balls" of a given size 1/L that can cover the figure at a given generation.

stage 1: N=2, L=2
stage 2: N=8, L=4
stage 3: N=32, L=8
stage n: $N=\frac12*4^n$, $L=2^n$

$D=\lim_{n\to\infty} \frac{\log(4^n/2)}{\log(2^n)}=\lim_{n\to\infty} \frac{n\log(4)-\log(2)}{n\log(2)}=\lim_{n\to\infty}\frac{\log(4)} {\log(2)}-\frac1n=2$

This seems a bit counterintuitive. It is easy to show that the linear length of the tree is infinite and the area containing it is finite, but I thought that since it appeared more complex than a simple line it would have dimension slightly greater than one. To think of this as a perfectly 2-dimensional object seems absurd.

If each left branch is assigned 0, and each right branch assigned 1, then the tree is topologically equivalent to the set of all possible infinite strings of 0 and 1, making it slightly larger than [0,1], furthering my suspicion that its dimension was slightly greater than 1.

Can someone verify this result?
• November 1st 2009, 10:40 AM
Laurent
Quote:

Originally Posted by Media_Man
Hello all. I am looking at branching binary trees in $\mathbb{R}^n$. Consider such a tree in which each branch is exactly twice the length of its two "child" branches. This can be defined iteratively as a self-similar fractal. I am trying to apply Hausdorff's rule of dimension represented by $N=L^D$, where N is the number of "balls" of a given size 1/L that can cover the figure at a given generation.

stage 1: N=2, L=2
stage 2: N=8, L=4
stage 3: N=32, L=8
stage n: $N=\frac12*4^n$, $L=2^n$

$D=\lim_{n\to\infty} \frac{\log(4^n/2)}{\log(2^n)}=\lim_{n\to\infty} \frac{n\log(4)-\log(2)}{n\log(2)}=\lim_{n\to\infty}\frac{\log(4)} {\log(2)}-\frac1n=2$

This seems a bit counterintuitive. It is easy to show that the linear length of the tree is infinite and the area containing it is finite, but I thought that since it appeared more complex than a simple line it would have dimension slightly greater than one. To think of this as a perfectly 2-dimensional object seems absurd.

If each left branch is assigned 0, and each right branch assigned 1, then the tree is topologically equivalent to the set of all possible infinite strings of 0 and 1, making it slightly larger than [0,1], furthering my suspicion that its dimension was slightly greater than 1.

Can someone verify this result?

First, a remark: you're talking of box dimension, not Hausdorff dimension, even though both coincide in a large variety of cases. In any case, it gives an upper bound for the Hausdorff dimension.

Then, I don't understand your numbers. I'd say $N_1=2$, $N_2=6$, $N_3=16$ where $N_n$ corresponds to a number of balls of radius $2^{-n}$. (If the tree is in a square of unit sidelength). And in general $N_{n+1}=2N_n+2^n$ hence you deduce $N_n=(n+1)2^{n-1}$. And $\frac{\log N_n}{\log L_n^{-1}}=\frac{\log((n+1)2^{n-1}}{\log{2^n}}\to_n 1$.

Another reason why it is 1 is because if you cut the tree in halfs you almost have the same tree divided by a factor 2. It should be $2^{1/d}$ for dimension $d$. (Think of integer values: you can cut a square in $4^n=2^{2n}$ parts that look like the square to the scale $1/2^n$). I don't have a theorem however to justify this.