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