[math-fun] Doin' the Hilbert walk
I've been spending quality time with Hilbert walks (finite approximations to Hilbert curves) in d-space lately (don't tell RWG), my ruminations somewhat inconvenienced by inability to locate a definition of what might actually constitute a Hilbert walk/curve in any dimension d > 2. Previous authors seem to cheerfully ignore the difficulty; or perhaps they just implicitly define a walk as being whatever convoluted Hmaitonian path their proposed algorithm happens to construct. While I have some ideas about an appropriate general definition, it's still not very clear to me exactly what properties --- combinatorial or possibly staistical --- of such a path might be significant in applications --- such as multiple-key database, and equation solving in many variables. Can anybody out there cast light on these matters? Fred Lunnon
On Thu, Aug 28, 2008 at 4:52 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
I've been spending quality time with Hilbert walks (finite approximations to Hilbert curves) in d-space lately (don't tell RWG), my ruminations somewhat inconvenienced by inability to locate a definition of what might actually constitute a Hilbert walk/curve in any dimension d > 2.
Previous authors seem to cheerfully ignore the difficulty; or perhaps they just implicitly define a walk as being whatever convoluted Hmaitonian path their proposed algorithm happens to construct.
While I have some ideas about an appropriate general definition, it's still not very clear to me exactly what properties --- combinatorial or possibly staistical --- of such a path might be significant in applications --- such as multiple-key database, and equation solving in many variables.
Can anybody out there cast light on these matters? Fred Lunnon
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 -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
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
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
On 8/29/08, Mike Stay <metaweta@gmail.com> wrote:
... 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!)
Interleaving does improve the locality over my crude base-(2^l) suggestion; 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.
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.
Sounds as if this might be the basis for the algorithm published by Butz in the 1970's, and unfortunately documented with the thoroughness customary in those primeval times --- which is to say, not! Do you have a reference? Bases other than 2 --- and possibly varying with the level --- is an obvious possibility as well; but I haven't investigated, and don't know of any applications. WFL
On Fri, Aug 29, 2008 at 11:09 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/29/08, Mike Stay <metaweta@gmail.com> wrote:
... 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!)
Interleaving does improve the locality over my crude base-(2^l) suggestion; 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.
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.
Sounds as if this might be the basis for the algorithm published by Butz in the 1970's, and unfortunately documented with the thoroughness customary in those primeval times --- which is to say, not! Do you have a reference?
No, sorry. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
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
On Fri, Aug 29, 2008 at 8:27 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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 !
It changes by one bit, and when you use the level n-1 code as the length along the axis, that means you change by one unit---i.e. you have to change it back from the Gray code for the offset to the standard binary code for the offset to see actual differences in position. Look at the diagram I drew: going from 00 to 10 doesn't jump by two cells. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
On 8/30/08, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Aug 29, 2008 at 8:27 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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 !
It changes by one bit, and when you use the level n-1 code as the length along the axis, that means you change by one unit---i.e. you have to change it back from the Gray code for the offset to the standard binary code for the offset to see actual differences in position. Look at the diagram I drew: going from 00 to 10 doesn't jump by two cells.
Aha --- light dawns at last! I hadn't taken in the significance of your first paragraph; and your diagram had been the subject of a visit from the proportional-spacing fairy. Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
On 8/30/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
I did so, but sad to say, still can't persuade this idea to work. Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view). y 7 000 6 010 5 011 4 001 3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited! Some direct d-space construction along these lines would be very nice to have --- and Butz did appear to have something of the sort, though quite elaborate and (apparently) a good deal slower than proves attainable by a more pedestrian method. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In the meantime, in answer to the problem posed by Joerg Arndt some time ago, here's a construction based on the paradigm I christen D0LEC (D0L-system, extended finally to a different alphabet, generator and extension morphisms both having constant width). Suppose the walk is required in 3-space. Generation morphism: use start symbol A,I,E at level = 0,1,2 mod 3 A -> E I I C C L L F B -> F J J D D K K E C -> G K K A A J J H D -> H L L B B I I G E -> I A A H H B B K F -> J B B G G A A L G -> K C C F F D D I H -> L D D E E C C J I -> A E E J J G G D J -> B F F I I H H C K -> C G G L L E E B L -> D H H K K F F A Extension morphism: abbreviating vector [x,y,z] to xyz A -> -000 +001 B -> -011 +010 C -> -110 +111 D -> -101 +100 E -> -000 +010 F -> -011 +001 G -> -110 +100 H -> -101 +111 I -> -000 +100 J -> -011 +111 K -> -110 +010 L -> -101 +001 Notice that D0L symbols correspond to lattice edges, rather than nodes! To compute the coordinate vector of the node n steps along the walk, generate the first n+1 symbols and map to vectors; trim off the first and last vectors, and sum the remainder. For instance let n = 10: applying the generator twice, E -> I A A H H B B K -> A E E J J G G D E I I ... the first 11 symbols of which extend (trimming both ends) to (-000) +001-000 +010-000 +010-011 +111-011 +111-110 +100-110 +100 -101 +100-000 +010-000 +100-000 (+100) = 310. Combining successive +- pairs in this way and summing gives step-by-step a Hilbert walk (one of many possible) in 3-space: 000, 001, 011, 010, 110, 111, 101, 100, 200, 210, 310, 300, 301, 311, 211, 201, 202, ... As presented above, the method is not terribly practical; however the D0LEC approach does permit very efficient (tho' more elaborate) algorithms, based on maintaining a running tree-branch structure, for navigating to the coordinate vector of n-th step and back again, in time and space logarithmic in the difference dn. It seems slightly inconvenient that the morphism is unstable: the starting symbol must be varied according to how many iterations are expected. It would be easy to correct this, but turns out to be a bad idea. For one thing, the result no longer reflects a geometric reality --- "inflating" a walk to the next level actually does alter the direction of the initial steps --- which in turn complicates inverse navigation unnecessarily. For another, the (hard-won) generator morphism symmetry is irretrievably destroyed --- as things stand, the symbols are transitive under isometries of the cube. The construction generalises to arbitrary dimension d; and the explicit order d 2^(d-1) D0LEC may be suppressed to save memory for higher d, incurring a relatively small time penalty, with all computations executed on-the-fly. Fred Lunnon
On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/30/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
I did so, but sad to say, still can't persuade this idea to work.
Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view).
y
7 000
6 010
5 011
4 001
3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x
Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited!
Right. The walk is done in 2-D for two iterations. You have to relabel the axes with an n-bit gray code (0,1)x(n-1-bit code) to get an n-iteration fractal: 000 000 (first bits are 0xx 0xx, then run the two-bit code forward) 000 001 001 001 001 000 001 010 001 011 000 011 000 010 010 010 010 011 011 011 011 010 011 000 011 001 010 001 010 000 010 100 (first bits are 0xx 1xx, then run the two-bit code backwards) ... 000 100 100 100 (first bits are 1xx 1xx, then run the two-bit code forwards) ... 110 100 110 000 (first bits are 1xx 0xx, then run the two-bit code backwards) ... 100 000
Some direct d-space construction along these lines would be very nice to have --- and Butz did appear to have something of the sort, though quite elaborate and (apparently) a good deal slower than proves attainable by a more pedestrian method.
This works for any number of dimensions. In 3d, the level-one fractal goes 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0 Next you tensor this pattern with itself to get x y z 00 00 00 00 00 01 00 01 01 00 01 00 01 01 00 01 01 01 01 00 01 01 00 00 01 00 10 etc., where the first bit of x, y, and z remain constant for eight steps while the second bit goes through the level-one pattern; then the first bits change and the second bits go backwards through the pattern. Rinse and repeat. I think your concern is that in the Hilbert fractal, the input and output are on the outside of the block instead of the inside, and can thus form a sub-block of the next iteration. This pattern doesn't have that property. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
Apparently my construction's called the Moore curve: http://en.wikipedia.org/wiki/Moore_curve On Sun, Sep 7, 2008 at 6:29 PM, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/30/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
I did so, but sad to say, still can't persuade this idea to work.
Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view).
y
7 000
6 010
5 011
4 001
3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x
Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited!
Right. The walk is done in 2-D for two iterations. You have to relabel the axes with an n-bit gray code (0,1)x(n-1-bit code) to get an n-iteration fractal:
000 000 (first bits are 0xx 0xx, then run the two-bit code forward) 000 001 001 001 001 000 001 010 001 011 000 011 000 010 010 010 010 011 011 011 011 010 011 000 011 001 010 001 010 000 010 100 (first bits are 0xx 1xx, then run the two-bit code backwards) ... 000 100 100 100 (first bits are 1xx 1xx, then run the two-bit code forwards) ... 110 100 110 000 (first bits are 1xx 0xx, then run the two-bit code backwards) ... 100 000
Some direct d-space construction along these lines would be very nice to have --- and Butz did appear to have something of the sort, though quite elaborate and (apparently) a good deal slower than proves attainable by a more pedestrian method.
This works for any number of dimensions. In 3d, the level-one fractal goes
0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
Next you tensor this pattern with itself to get
x y z 00 00 00 00 00 01 00 01 01 00 01 00 01 01 00 01 01 01 01 00 01 01 00 00 01 00 10 etc., where the first bit of x, y, and z remain constant for eight steps while the second bit goes through the level-one pattern; then the first bits change and the second bits go backwards through the pattern.
Rinse and repeat.
I think your concern is that in the Hilbert fractal, the input and output are on the outside of the block instead of the inside, and can thus form a sub-block of the next iteration. This pattern doesn't have that property. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
I have a slightly idiosyncratic take on Hilbert curves which may be of interest. Specifically, I think of them of morphisms from fractal lines to fractal cubes. For example, I think of the original 2d Hilbert curve as the morphism F such that F(x -> 1/4x) = 1/2 (y,x) F(x -> 1/4x + 1/4) = 1/2 (x,y) + (0,1/2) F(x -> 1/4x + 2/4) = 1/2 (x,y) + (1/2,1/2) F(x -> 1/4x + 3/4) = 1/2 (1-y,x) + (1/2,0) What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...)))) Such a morphism on transformations then induces a continuous mapping on the geometric fractals (the attractors of the transformations, to use Iterated Function System lingo). Anyway, there are plenty of morphisms from the octadic line to an eight transformation fractal cube. For example F(1/8x) = 1/2 (y,x,z) F(1/8x + 1/8) = 1/2(z,y,x) + (0,1/2,0) F(1/8x + 2/8) = 1/2(z,y,x) + (0,1/2,1/2) F(1/8x + 3/8) = 1/2(x,1-y,1-z) + (0,0,1/2) F(1/8x + 4/8) = 1/2(x,1-y,1-z) + (1/2,0,1/2) F(1/8x + 5/8) = 1/2(1-z,y,x) + (1/2,1/2,1/2) F(1/8x + 6/8) = 1/2(1-z,y,x) + (1/2,1/2,0) F(1/8x + 7/8) = 1/2(1-y,x,z) + (1/2,0,0) -Thomas C On Sun, Sep 7, 2008 at 9:41 PM, Mike Stay <metaweta@gmail.com> wrote:
Apparently my construction's called the Moore curve: http://en.wikipedia.org/wiki/Moore_curve
On Sun, Sep 7, 2008 at 6:29 PM, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/30/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Yes, that's quite ingenious. I must go away and quietly digest it ... WFL
I did so, but sad to say, still can't persuade this idea to work.
Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view).
y
7 000
6 010
5 011
4 001
3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x
Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited!
Right. The walk is done in 2-D for two iterations. You have to relabel the axes with an n-bit gray code (0,1)x(n-1-bit code) to get an n-iteration fractal:
000 000 (first bits are 0xx 0xx, then run the two-bit code forward) 000 001 001 001 001 000 001 010 001 011 000 011 000 010 010 010 010 011 011 011 011 010 011 000 011 001 010 001 010 000 010 100 (first bits are 0xx 1xx, then run the two-bit code backwards) ... 000 100 100 100 (first bits are 1xx 1xx, then run the two-bit code forwards) ... 110 100 110 000 (first bits are 1xx 0xx, then run the two-bit code backwards) ... 100 000
Some direct d-space construction along these lines would be very nice to have --- and Butz did appear to have something of the sort, though quite elaborate and (apparently) a good deal slower than proves attainable by a more pedestrian method.
This works for any number of dimensions. In 3d, the level-one fractal goes
0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
Next you tensor this pattern with itself to get
x y z 00 00 00 00 00 01 00 01 01 00 01 00 01 01 00 01 01 01 01 00 01 01 00 00 01 00 10 etc., where the first bit of x, y, and z remain constant for eight steps while the second bit goes through the level-one pattern; then the first bits change and the second bits go backwards through the pattern.
Rinse and repeat.
I think your concern is that in the Hilbert fractal, the input and output are on the outside of the block instead of the inside, and can thus form a sub-block of the next iteration. This pattern doesn't have that property. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 9/8/08, Thomas Colthurst <thomaswc@gmail.com> wrote:
I have a slightly idiosyncratic take on Hilbert curves which may be of interest.
Specifically, I think of them of morphisms from fractal lines to fractal cubes.
For example, I think of the original 2d Hilbert curve as the morphism F such that F(x -> 1/4x) = 1/2 (y,x) F(x -> 1/4x + 1/4) = 1/2 (x,y) + (0,1/2) F(x -> 1/4x + 2/4) = 1/2 (x,y) + (1/2,1/2) F(x -> 1/4x + 3/4) = 1/2 (1-y,x) + (1/2,0)
What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
Such a morphism on transformations then induces a continuous mapping on the geometric fractals (the attractors of the transformations, to use Iterated Function System lingo). ...
Presumably "morphism" means function(al) transforming (geometric) mappings, but with some extra constraint: along the lines of F(g(f)) = g(F(f)), for g in some (other) class of mappings perhaps? But I'm still confused: is "x" on the LHS above the same as on the RHS --- in which case, where did "y" spring from? Or should there be some other variable t on the LHS, with (implicitly) forward and reverse mappings from t to [x,y]?
What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
This certainly looks intriguing; but I must request more explanation, please! ---------------------------------------- Or I could take the initiative, and instead ask: does your paradigm cast any light on the "indexing" problem: to develop algorithms which approximately evaluate the d-space coordinate vector along the Hilbert curve as a function of the 1-space enumeration variable, together with the inverse function, in (amortised) time logarithmic in the length of any subinterval to which the variable is restricted? [Since the inverse function is discontinuous, this ambition may require modification to become practicable.] The efficient indexing point of view --- discretely, at any rate --- can be profitably be taken of other combinatorial problems besides Hilbert walk: permutations and combinations etc, and Tower of Hanoi and its derivatives come at once to mind. In the classical ToH for example, so beloved of elementary computer programming instructors, this approach uncovers an unexpected constant-time algorithm for enumeration, along with a mapping from legal configurations to consecutive natural numbers which improves the storage requirements of tree-searching computations involving ToH. On another note, it's claimed in a couple of internet articles that the Hilbert curve is "self-intersecting" (by somebody-or-other's theorem). Presumably what they mean is that it touches itself (which it obviously does, at any point with finite binary coordinates) rather than crossing itself (which it obviously does not). Can anybody out there elucidate? Fred Lunnon
On Wed, Sep 10, 2008 at 3:14 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 9/8/08, Thomas Colthurst <thomaswc@gmail.com> wrote:
I have a slightly idiosyncratic take on Hilbert curves which may be of interest.
Specifically, I think of them of morphisms from fractal lines to fractal cubes.
For example, I think of the original 2d Hilbert curve as the morphism F such that F(x -> 1/4x) = 1/2 (y,x) F(x -> 1/4x + 1/4) = 1/2 (x,y) + (0,1/2) F(x -> 1/4x + 2/4) = 1/2 (x,y) + (1/2,1/2) F(x -> 1/4x + 3/4) = 1/2 (1-y,x) + (1/2,0)
The RHS of each of these should have a (x,y) -> at their beginning.
What makes it a morphism is that it preserves relations between
"addresses"
in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
Such a morphism on transformations then induces a continuous mapping on the geometric fractals (the attractors of the transformations, to use Iterated Function System lingo). ...
Presumably "morphism" means function(al) transforming (geometric) mappings, but with some extra constraint: along the lines of F(g(f)) = g(F(f)), for g in some (other) class of mappings perhaps?
But I'm still confused: is "x" on the LHS above the same as on the RHS --- in which case, where did "y" spring from? Or should there be some other variable t on the LHS, with (implicitly) forward and reverse mappings from t to [x,y]?
Sorry, I wasn't very clear at all. Let me start over. Take a finite set of contractive transformations T. Then there is an unique compact set A_T such that A_T = union_i T_i(A_T). Call it "T's attractor". For example, for T = {x -> 1/4x + i/4, i = 0 .. 3}, A_T = [0,1]. For T = {(x,y) -> 1/2 (x,y) + 1/2(i,j), i = 0 .. 1, j = 0 .. 1}, A_T = [0,1] x [0,1]. Here's another way to think of A_T: Take an infinite sequence of transformations, each chosen from T, and compose them all in order. The resulting transformation will be of the form x -> p for some p in A_T. Call the infinite sequence of transformations that results in x -> p "an address for p". A point can have multiple addresses and in fact unless A_T is a Cantor set, some point in A_T will have multiple addresses. Perhaps the most familiar example of multiple addresses is when T = {x -> 1/10 x + i/10, i = 0 .. 9}, then if we let i stand for T_i we have 0 o 9 o 9 o 9 o ... = 1 o 0 o 0 o 0 o ... (where I'm using "o" as the composition operator) because both are addresses for 0.1. We are now ready to talk about morphisms between fractals. F:T -> S is simply a mapping between the finite sets T and S with the additional requirement that it preserves any address overlaps from T: if t_1 o t_2 o t_3 o ... = t_1' o t_2' o t_3' o ... for t_i and t_i in T, then F(t_1) o F(t_2) o F(t_3) o ... = F(t_1') o F(t_2') o F(t_3') o ...
What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
This certainly looks intriguing; but I must request more explanation, please!
----------------------------------------
Or I could take the initiative, and instead ask: does your paradigm cast any light on the "indexing" problem: to develop algorithms which approximately evaluate the d-space coordinate vector along the Hilbert curve as a function of the 1-space enumeration variable, together with the inverse function, in (amortised) time logarithmic in the length of any subinterval to which the variable is restricted? [Since the inverse function is discontinuous, this ambition may require modification to become practicable.]
Yes. I believe that any fractal morphism from T_d = {x -> 1/d x + i/d, i = 0 .. d-1 } to a fractal cube will support this sort of indexing. Given a point in [0,1], simply take its address (i.e., its base d expansion) to the desired accuracy, then translate this address prefix with F to get the sub-cube address prefix. The only slight complication is that each transformation of the fractal cube will look something like x -> 1/2 R(x) + 1/2 j where j is a vector with 0/1 entries and R is a symmetry of the cube, so you'll have to compose the various R's after you translate. The inverse mapping works similarly, except that you'll have to tile the region of the cube you want mapped with subcubes. -Thomas C
The efficient indexing point of view --- discretely, at any rate --- can be profitably be taken of other combinatorial problems besides Hilbert walk: permutations and combinations etc, and Tower of Hanoi and its derivatives come at once to mind.
In the classical ToH for example, so beloved of elementary computer programming instructors, this approach uncovers an unexpected constant-time algorithm for enumeration, along with a mapping from legal configurations to consecutive natural numbers which improves the storage requirements of tree-searching computations involving ToH.
On another note, it's claimed in a couple of internet articles that the Hilbert curve is "self-intersecting" (by somebody-or-other's theorem). Presumably what they mean is that it touches itself (which it obviously does, at any point with finite binary coordinates) rather than crossing itself (which it obviously does not). Can anybody out there elucidate?
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 9/8/08, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Sep 7, 2008 at 12:31 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Accepting for the moment that the origin must be chosen carefully, trying to extend the construction to 8x8 in 2-space leads to essentially the "letter H" diagram MS showed earlier for 4x4 (switch off propotional spacing to view).
y
7 000
6 010
5 011
4 001
3 101 o---o o---o | | | | 2 100 o o o o | | 1 110 o o---o o | | | | 0 111 o---o o---o 111 110 100 101 001 011 010 000 0 1 2 3 4 5 6 7 x
Now the problem is, where can the walk go after (x,y) = (2,2)? It is entirely surrounded by nodes which have already been visited!
Right. The walk is done in 2-D for two iterations. You have to relabel the axes with an n-bit gray code (0,1)x(n-1-bit code) to get an n-iteration fractal: ... I think your concern is that in the Hilbert fractal, the input and output are on the outside of the block instead of the inside, and can thus form a sub-block of the next iteration. This pattern doesn't have that property.
I had realised that, and it is not the point I am making. I constructed in full the same 2-space level-3 list as you sketched, reversing the Gray-codes back to coordinates as indicated in my diagram above [but complemented first, in order to place the origin at a corner]. After [2,2] the next node indicated by the scheme is [7,2] (or 000 100). Looking back, I now suspect that you may have confused the assertions "consecutive integers map to Gray codes differing by a single bit" (true) and "Gray codes differing by a single bit map to consecutive integers" (false).
Apparently my construction's called the Moore curve: http://en.wikipedia.org/wiki/Moore_curve
Googling away on this hint turned up also Robert Dickau "Hilbert and Moore Curves" http://www.prairienet.org/~pops/hilbert3d.html http://mathforum.org/advanced/robertd/lsys2d.html V. B. Balayoghan http://www.cs.utexas.edu/users/vbb/misc/sfc/Oindex.html Looking at the pictures reveals immediately that the level-l Moore walk in 2-space is essentially four Hilbert level-(l-1) walks, oriented differently from Hilbert level-l and re-connected; it's not hard to imagine an analogous construction in d-space. A WFL-style D0LEC structure looks a tad more involved than for Hilbert: in particular, it seems the morphisms must differ between odd / even levels, with stability impossible to pre- or post-engineer across them. It's also noteworthy that no D0L system is offered for the Moore walk by other sources; my conclusion is that it is actually a somewhat more complicated object than the Hilbert walk. Fred Lunnon
On 9/8/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
... [but complemented first, in order to place the origin at a corner].
Oops --- dodgy --- binary complement does not commute with Gray-code! But if we just try to play it straight, it already falls over for 4x4: Gray 000 001 011 010 110 111 101 100 x/y ___0 __1 __2 __3 __4 __5 __6 __7 000 000 [0,0] 000 001 [0,1] 001 001 [1,1] 001 000 [1,0] 001 010 [1,3] ?? 001 011 [1,2] 000 011 [0,2] 000 010 [0,3] 010 010 [3,3] 010 011 [3,2] 011 011 [2,2] 011 010 [2,3] 011 000 [2,0] 011 001 [2,1] 010 001 [3,1] 010 000 [3,0] WFL
participants (3)
-
Fred lunnon -
Mike Stay -
Thomas Colthurst