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! 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In the meantime, in answer to the problem posed by Joerg Arndt some time ago, here's a construction based on the paradigm I christen D0LEC (D0L-system, extended finally to a different alphabet, generator and extension morphisms both having constant width). Suppose the walk is required in 3-space. Generation morphism: use start symbol A,I,E at level = 0,1,2 mod 3 A -> E I I C C L L F B -> F J J D D K K E C -> G K K A A J J H D -> H L L B B I I G E -> I A A H H B B K F -> J B B G G A A L G -> K C C F F D D I H -> L D D E E C C J I -> A E E J J G G D J -> B F F I I H H C K -> C G G L L E E B L -> D H H K K F F A Extension morphism: abbreviating vector [x,y,z] to xyz A -> -000 +001 B -> -011 +010 C -> -110 +111 D -> -101 +100 E -> -000 +010 F -> -011 +001 G -> -110 +100 H -> -101 +111 I -> -000 +100 J -> -011 +111 K -> -110 +010 L -> -101 +001 Notice that D0L symbols correspond to lattice edges, rather than nodes! To compute the coordinate vector of the node n steps along the walk, generate the first n+1 symbols and map to vectors; trim off the first and last vectors, and sum the remainder. For instance let n = 10: applying the generator twice, E -> I A A H H B B K -> A E E J J G G D E I I ... the first 11 symbols of which extend (trimming both ends) to (-000) +001-000 +010-000 +010-011 +111-011 +111-110 +100-110 +100 -101 +100-000 +010-000 +100-000 (+100) = 310. Combining successive +- pairs in this way and summing gives step-by-step a Hilbert walk (one of many possible) in 3-space: 000, 001, 011, 010, 110, 111, 101, 100, 200, 210, 310, 300, 301, 311, 211, 201, 202, ... As presented above, the method is not terribly practical; however the D0LEC approach does permit very efficient (tho' more elaborate) algorithms, based on maintaining a running tree-branch structure, for navigating to the coordinate vector of n-th step and back again, in time and space logarithmic in the difference dn. It seems slightly inconvenient that the morphism is unstable: the starting symbol must be varied according to how many iterations are expected. It would be easy to correct this, but turns out to be a bad idea. For one thing, the result no longer reflects a geometric reality --- "inflating" a walk to the next level actually does alter the direction of the initial steps --- which in turn complicates inverse navigation unnecessarily. For another, the (hard-won) generator morphism symmetry is irretrievably destroyed --- as things stand, the symbols are transitive under isometries of the cube. The construction generalises to arbitrary dimension d; and the explicit order d 2^(d-1) D0LEC may be suppressed to save memory for higher d, incurring a relatively small time penalty, with all computations executed on-the-fly. Fred Lunnon