[math-fun] Space-filling curves
I think I have a new integer sequence for the OEIS (although please tell me if it seems insufficiently interesting). But first, a question: Is there a standard way to encode the cardinal directions as integers? I picked mine since it's both the standard clockwise N,E,S,W and because in this particular case it encodes the first three directions as 1,2,3. Encode up=1, right=2, down=3, left=4. The sequence is the directions of travel of a Hilbert curve as it leaves the origin. I rather arbitrarily used this as the shape of the second iteration. Here again, maybe someone can tell me if there's a more conventional form. p m l k o n i j b c h g a d e f ^ Given these two conventions, the sequence would begin: 1,2,3,2,2,1,4,1,2,1,4,4,3,4,1,... [a->b c d e f g h i j k l m n o p] Can somebody point me at the right vocabulary for thinking about the mappings of 1234 to NESW? It's rather arbitrary, and if your compass is rotated from mine so that you think 2341=NESW, 3412=NESW and 4123=NESW, you'll still get a Hilbert curve, but if you use 1324=NESW, your lines won't connect when you use my sequence. So, there's a relationship inherent in those rotations such that 3=-1 and 2=-4, and that makes me think that group theory ought to be involved. What about sequences of symbols which are totally, er, unrelated? Unordered? That is, assume I have a sequence a,b,c,b,b,d,a that I consider equivalent to the set of all sequences f(a),f(b),f(c),f(b),f(b),f(d),f(a) in which f() is a bijection from {a,b,c,d}->{a,b,c,d}. (In other words, totally arbitrarily chosen symbols.) Would it make sense to want an Online Encyclopedia of such sequences in which the symbols don't have a relationship like the integers do? Or is there a way to canonicalize such sequences so that we can express them uniquely as integers? Perhaps we could force the convention that the symbols must be numbered in order, so that 1 is always the first number to appear in the sequence and that the next non-1 symbol must be 2, etc.? (Sorry if this is an excessivly elementary subject to be asking about)
When I was doing things like that, I decided that a good, compact encoding was to represent turns rather than compass directions. It assumes that a step in the chain never (or rarely) reverses the previous one, that is, isn't usually 180 degrees from the previous step. Then you can use 2=straight, 3=turn left, 1=turn right, and 0=break (the next code being stop, reverse, etc.). Subtracting 2 gives the direction change in multiples of 180. Steve Gray -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Jason Sent: Sunday, March 30, 2008 1:26 AM To: math-fun@mailman.xmission.com Subject: [math-fun] Space-filling curves I think I have a new integer sequence for the OEIS (although please tell me if it seems insufficiently interesting). But first, a question: Is there a standard way to encode the cardinal directions as integers? I picked mine since it's both the standard clockwise N,E,S,W and because in this particular case it encodes the first three directions as 1,2,3. Encode up=1, right=2, down=3, left=4. The sequence is the directions of travel of a Hilbert curve as it leaves the origin. I rather arbitrarily used this as the shape of the second iteration. Here again, maybe someone can tell me if there's a more conventional form. p m l k o n i j b c h g a d e f ^ Given these two conventions, the sequence would begin: 1,2,3,2,2,1,4,1,2,1,4,4,3,4,1,... [a->b c d e f g h i j k l m n o p] Can somebody point me at the right vocabulary for thinking about the mappings of 1234 to NESW? It's rather arbitrary, and if your compass is rotated from mine so that you think 2341=NESW, 3412=NESW and 4123=NESW, you'll still get a Hilbert curve, but if you use 1324=NESW, your lines won't connect when you use my sequence. So, there's a relationship inherent in those rotations such that 3=-1 and 2=-4, and that makes me think that group theory ought to be involved. What about sequences of symbols which are totally, er, unrelated? Unordered? That is, assume I have a sequence a,b,c,b,b,d,a that I consider equivalent to the set of all sequences f(a),f(b),f(c),f(b),f(b),f(d),f(a) in which f() is a bijection from {a,b,c,d}->{a,b,c,d}. (In other words, totally arbitrarily chosen symbols.) Would it make sense to want an Online Encyclopedia of such sequences in which the symbols don't have a relationship like the integers do? Or is there a way to canonicalize such sequences so that we can express them uniquely as integers? Perhaps we could force the convention that the symbols must be numbered in order, so that 1 is always the first number to appear in the sequence and that the next non-1 symbol must be 2, etc.? (Sorry if this is an excessivly elementary subject to be asking about) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My simple-minded attempts at various ways to compute (or represent) the 2D curve are given in http://www.jjj.de/fxt/#fxtbook (go for the index entry "Hilbert curve"). I found that the moves are a simpler device than the turns (left, right, straight), see e.g. sections 36.9 "A function that encodes the Hilbert curve" (p.734) and 36.9.2 "The turns of the Hilbert curve" (p.736). I'd much like to see a generalization of the string substitution rules for the 2D curve, a --> -bF+aFa+Fb- b --> +aF-bFb-Fa+ + --> + - --> - F --> F (start with "a"), for higher dimensions. At least for 3D. It seems one needs more that 3 nontrivial rules (and non-drawing symbols, generalizing "a" and "b" above; do 6 suffice?). Yes I know of methods for 3D ones, like the obscure string substitution "a" --> "^<aF^<aFa-F^>>aFavF+>>aFa-F>a->", // "draw": "F" --> "F", // rotations: "+" --> "+", // +z "-" --> "-", // -z "^" --> "^", // +y "v" --> "v", // -y "<" --> "<", // +x ">" --> ">" // -x (can someone render this more symmetrical/clear?) ... and Butz' algorithm for all dimension (which I completely fail to understand). Any technique to find morphisms (string substitutions) for a given (sufficiently long) string would also be helpful. just my 2 nano-cents P.S.: is there any paper dealing with three- or higher dimensional Hilbert curves that is not totally obscure? * Stephen Gray <stevebg@roadrunner.com> [Mar 31. 2008 09:21]:
[... Hilbert curve ...]
participants (3)
-
Jason -
Joerg Arndt -
Stephen Gray