On 8/30/08, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Aug 29, 2008 at 11:09 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
but I think one essential property of any generalisation must be that the resulting walk is Hamiltonian --- each step altering just one coordinate by (+/-)1 --- which this construction fails to enforce.
It inherits it from the fact that the original walk is a Gray code, which has that property.
I think not. Quoting from your example, lines 4-5 01 00 01 10 (first bit is 01, second bit goes 10,11,01,00) the second vector component increments by +2 ! Returning to attempting to pin these things down properly, I suggested: A "Hilbert walk" traversing a cell is defined as a Hamiltonian path of the cell such that (i) entry and exit are at (specific) neighbouring vertices of the enclosing hypercube; (ii) each sub-cell is traversed by a Hilbert walk; (iii) the sub-cell origins in order visited traverse an (isometric transformation of the canonical) Gray path along the edges of a unit hypercube. A couple of comments seem to be called for. Firstly, the definition is more transparent if the induction is reversed: specify that each level-1 sub-cell must be traversed by a Gray-code style path, then deflate those cells to their origins and specify that the resulting level-(l-1) walk is Hilbert. Secondly, specifying Gray paths at level-1, and corner entry/exit [which may be redundant], permits a construction inflating any given walk to level-(l+1) --- I don't know whether this can be guaranteed under more relaxed constraints. WFL