On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/30/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
I did so, but sad to say, still can't persuade this idea to work.
Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view).
y
7 000
6 010
5 011
4 001
3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x
Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited!
Right. The walk is done in 2-D for two iterations. You have to relabel the axes with an n-bit gray code (0,1)x(n-1-bit code) to get an n-iteration fractal: 000 000 (first bits are 0xx 0xx, then run the two-bit code forward) 000 001 001 001 001 000 001 010 001 011 000 011 000 010 010 010 010 011 011 011 011 010 011 000 011 001 010 001 010 000 010 100 (first bits are 0xx 1xx, then run the two-bit code backwards) ... 000 100 100 100 (first bits are 1xx 1xx, then run the two-bit code forwards) ... 110 100 110 000 (first bits are 1xx 0xx, then run the two-bit code backwards) ... 100 000
Some direct d-space construction along these lines would be very nice to have --- and Butz did appear to have something of the sort, though quite elaborate and (apparently) a good deal slower than proves attainable by a more pedestrian method.
This works for any number of dimensions. In 3d, the level-one fractal goes 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0 Next you tensor this pattern with itself to get x y z 00 00 00 00 00 01 00 01 01 00 01 00 01 01 00 01 01 01 01 00 01 01 00 00 01 00 10 etc., where the first bit of x, y, and z remain constant for eight steps while the second bit goes through the level-one pattern; then the first bits change and the second bits go backwards through the pattern. Rinse and repeat. I think your concern is that in the Hilbert fractal, the input and output are on the outside of the block instead of the inside, and can thus form a sub-block of the next iteration. This pattern doesn't have that property. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com