On 9/8/08, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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: ... 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.
I had realised that, and it is not the point I am making. I constructed in full the same 2-space level-3 list as you sketched, reversing the Gray-codes back to coordinates as indicated in my diagram above [but complemented first, in order to place the origin at a corner]. After [2,2] the next node indicated by the scheme is [7,2] (or 000 100). Looking back, I now suspect that you may have confused the assertions "consecutive integers map to Gray codes differing by a single bit" (true) and "Gray codes differing by a single bit map to consecutive integers" (false).
Apparently my construction's called the Moore curve: http://en.wikipedia.org/wiki/Moore_curve
Googling away on this hint turned up also Robert Dickau "Hilbert and Moore Curves" http://www.prairienet.org/~pops/hilbert3d.html http://mathforum.org/advanced/robertd/lsys2d.html V. B. Balayoghan http://www.cs.utexas.edu/users/vbb/misc/sfc/Oindex.html Looking at the pictures reveals immediately that the level-l Moore walk in 2-space is essentially four Hilbert level-(l-1) walks, oriented differently from Hilbert level-l and re-connected; it's not hard to imagine an analogous construction in d-space. A WFL-style D0LEC structure looks a tad more involved than for Hilbert: in particular, it seems the morphisms must differ between odd / even levels, with stability impossible to pre- or post-engineer across them. It's also noteworthy that no D0L system is offered for the Moore walk by other sources; my conclusion is that it is actually a somewhat more complicated object than the Hilbert walk. Fred Lunnon