On 9/19/08, Steve Witham <sw@tiac.net> wrote:
Found this page:
http://people.csail.mit.edu/jaffer/Geometry/HSFC
Pretty much searching for "Butz Hilbert".
Very useful page --- wonder why didn't I manage to find it earlier?
Jaffer complains that the existing implementations of Butz's multi-dimensional Hilbert curve algorithm 1) are hard to read, 2) take the number of bits of precision as an argument (instead of letting it be whatever the arguments require), and 3) are limited by the precision of the representations they use for distance-along-curve, for instance to 32 bits, for the product (number of dimensions x bits of resolution in each).
As well as that some are unstable --- increasing the level altering the initial steps.
So, he develops a Scheme algorithm that uses bignums and works "in terms of higher level constructs: Gray-code, lamination, rotation and reflection."
Unfortunately, unless one speaks "Scheme"(?), it's fairly incomprehensible; and AJ is fares no better than anybody else does (self included, so far!) at giving a coherent description of his algorithm [artificially slowed and complicated by an absence of decent "bitwise" logical operators]. In particular, he fails to define "lamination" --- however, later on he does say "Gray codes find use communicating incrementally changing values between asynchronous agents. De-laminated Gray codes comprise the coordinates of Hilbert space-filling curves." This sounds to be pretty much the same idea that Mike Stay talked about earlier!
This sounds like the right approach to me (although it might need optimizing/obfuscating again in the end), but I'm still having problem 1) at the moment. Here's the main routine (mainly to show its length): ...
[There is a link to the entire program for forward and reverse navigation.]
Further rationale: http://people.csail.mit.edu/jaffer/Geometry/RFMDSFF
Including a the following thoughtful list of desirable properties for a space-filler: "Space-filling: a continuous function whose range contains the entire n-dimensional unit hypercube. Multidimensional: exist for all ranks greater than one. Self-similar: can be defined by a nonterminating recurrence. Lebesgue measure-preserving: equal length intervals map to equal volumes. Isotropic: the lengths of axis-aligned projections of the space-filling curve should be equal." But alas, still no definition of a "Hilbert curve" ... Jaffer gives a short bibliography, including Rolf Niedermeier, Jochen Alber "On Multi-dimensional Hilbert Indexings" COCOON '98 Springer (1998) who apparently have got some sort of definition, and (remarkably) claim "our analysis shows that there are 1536 structurally different 3D Hilbert curves" at which the imagination boggles (and may be better to remain that way). There are also references to a business-like C-program by Doug Moore at http://web.archive.org/web/20050204100342/http://www.caam.rice.edu/~dougm/tw... who includes what Jaffer christens "box" and "comparison" functions, and an experimental comparison of the clustering behaviour. Although the algorithm is undocumented, its general shape is similar enough to my effort to suggest that the time and space costs should be comparable (if/when we get around to C-ifying the Java code). (Curses!).
Also, He develops a Peano-curve-based method that fills all space instead of just a >=0 corner. He measures distance on the curve vs. Euclidean distance for various curves.
Some of these studies mention that the performance of different methods tends to converge for higher dimensions. I wonder if they have taken account of the fact that, for a fixed diameter region, the average level rapidly approaches unity as the dimension increases --- so that the "walk" becomes effectively a Gray coded path around the unit hypercube. A nice project would be to implement the various available algorithms in the same language (probably C), and compare their performance wrt time, space, clustering. Fred Lunnon