We are interested in the family of space-filling curves with edges between the greatest possible number of nearest neighbours in the space. Since the curves are one-dimensional, this number must be 2. The curves are the family of "Hilbert curves".

The PostScript file Hilbert Order in d Dimensions (161 Kbytes) is a ten-page derivation of the mapping between Hilbert order and coordinates in any number of dimensions for any order of curve.

Bially's paper, Space-filling curves: their generation and their application to bandwidth reduction (IEEE Transactions on Information Theory, IT-15, 6(Nov. 1969) 658-64) is more general, in that it develops a base hypercube of size m*m*..*m for any m, instead of just m=2. Bially expresses his mappings between position on the curve and spatial coordinates with a series of state diagrams, examples of which he shows in two and three dimensions, and an abstraction for four. We use a single set of rules for any number of dimensions as well as for any order.

Curves connecting only nearest neighbours in more than two dimensions are not unique. We have one, based on a binary reflective Gray code [C. Faloutsos, Gray codes for partial match and range queries, IEEE Trans. on Software Engineering, 14 10(Oct., 1988) 1381-9] and extended by reflections. Bially has another. Jagadish (Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990, Hector Garcia-Molina and H. V. Jagadish, eds., 332-42) shows a third, in 3-D, and Gilbert shows a fourth 3-D Hilbert curve.

Merrett's home page