Use the level n-1 code to mark off distance along each axis. Since a gray code returns to itself, it really is marking off distance on a d-dimensional hypertorus. To get a level n gray code, you tensor the level 0 sequence with the level n-1 sequence, where "tensor" here means the first bit of each coordinate follows the level zero sequence, while the rest go back and forth through the level n-1 before the first bit changes. 00 00 (first bit is 00, second bit goes 00,01,11,10) 00 01 01 01 01 00 01 10 (first bit is 01, second bit goes 10,11,01,00) 01 11 00 11 00 10 10 10 (first bit is 11, second bit goes 00,01,11,10) 10 11 11 11 11 10 11 00 (first bit is 10, second bit goes 10,11,01,00) 11 01 10 01 10 00 01+-+ +-+ | | | | 00| + + + | | 10+ +-+ + | | | | 11+-+ +-+ 11100001 This isn't the usual Hilbert curve, but it does touch each space once and, because of the tensor, stays local. (And it looks like an H for Hilbert!) To get the usual one, you use a slightly more complicated tensor product involving some swapping of bits and xors. But since you want to generalize to other dimensions and bases, I suggest using the simple algorithm described above. On Thu, Aug 28, 2008 at 9:02 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/29/08, Mike Stay <metaweta@gmail.com> wrote:
Gray codes! The nth approximation to a Hilbert curve in d-dimensional space is an (nd)-bit Gray code. http://en.wikipedia.org/wiki/Gray_code
I can't see how this claim can be true in any algorithmically meaningful way, even for 2-space --- though I should be delighted to be proved wrong! How for example would you propose to map the 4-digit base-2 Gray code 00 01 03 02 12 13 11 10 30 32 33 31 21 23 22 20 --- or, more plausibly, the 2-digit base-4 code 00 01 02 03 13 12 11 10 20 21 22 23 33 32 31 30 to the level-2 plane Hilbert walk 00 10 11 01 02 03 13 12 22 23 33 32 31 21 20 30 ?
Apparently higher-radix Gray codes have previously also been employed for the same applications --- being for one thing (much) easier to construct --- but are considered inferior, on the grounds that clustering in the data is badly preserved by the mapping.
In contrast, a Hilbert map tends to "hang around" in one region, exhausting that before moving on to the next --- one of the characteristics I had in mind in my earlier posting.
[You gave me a bad moment there, Mike --- I'd just finished spending 2 months developing a fast d-space Hilbert-walk algorithm --- and it was a royal pain!]
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com