Peano monster curve (idea)

A pretty good writeup by Yuri Prime, and a pretty awful ASCII diagram for people like me who don't have a monster-wide monitor screen. As a public service, here are some smaller, neater diagrams:

+-----------------------+
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
|                       |
| ---------->---------- |
|/                     \|
+-----------------------+

+-----------+-----+-----+
|           |     |     |
|           |     |     |
|           |     |     |
|           | ->- | ->- |
|           |/   \|/   \|
|           |-----+-----+
|           |\    |    /|
|           | |   |   | |
|           | ^   |   v |
| ---->---- | |   |   | |
|/         \|/    |    \|
+-----+-----+-----+-----+
|\   /|\    |          /|
| -<- | |   |         | |
|     | ^   |         | |
|     | |   |         | |
|     |/    |         | |
+-----+-----+         v |
|     |\    |         | |
|     | |   |         | |
|     | ^   |         | |
| ->- | |   |         | |
|/   \|/    |          \|
+-----+-----+-----------+


                   / 
                  /  
                 /   
                /    
               /     
             -/      
             /|      
            /        
           /         
          1          
         /           
        /            
       /             
      /              
     /               
    /                
   /                 
  /                  
 /                   

      --            /
    -/  \         -/ 
    /|   \        /| 
   3      4      9   
  /        \|   /    
 /         -\  /     
(            )(      
 \-         /  \-    
 |\        /   |\    
   2      5      8   
    \   |/        \  
     \  /-         \ 
      )(            )
    -/  \         -/ 
    /|   \        /| 
   1      6      7   
  /        \|   /    
 /         -\  /     
/            --      

Another way of thinking of a surjective map from [0, 1] to [0, 1]² is to again consider the decimal expansion (or binary expansion, or any base) 0.d₁d₂d₃d₄… and split it up into two numbers, 0.d₁d₃… with all the odd-positioned digits and 0.d₂d₄… with all the even-positioned digits. It doesn't work as a curve, though, because two numbers 'near' each other in the [0, 1] 'linear' space need not be near each other in the [0, 1]² 'planar' space. Similarly, [0, 1] can be mapped to [0, 1]³ by taking every third digit at a different 'phase' for each dimension, or [0, 1]⁴, or [0, 1]ⁿ for any positive integer n.

The first step of the diagonal version of the Peano monster curve can be generalised to 3-D quite easily; consider a 3*3*3 stack of cubes. The lowest 3*3 'slice', as viewed from above, will look exactly like the first step of the 2D Peano monster curve. The bottom-left, where the curve starts, will be on the lower corner, the end of the first segment will be at the upper corner, and the curve alternates between the lower plane and the upper plane for each segment. This ends up at the upper top-right corner of the lowest slice of the cube, which is the same point as the lower top-right corner of the middle slice. The middle slice looks like the bottom slice, rotated through half a revolution - this time, the curve retraces backwards along the 2D shape as viewed from above, again alternating between the lower plane and the upper plane of the middle slice. This ends in the upper bottom-left corner of the middle slice, or the lower bottom-left corner of the highest slice. The highest slice is identical to the lowest slice, ending at the upper top-right corner.

Formally, this sequence can be generalised as follows:

Imagine a sequence of functions, f_n(x, i), n being a positive integer, x being an integer between 0 and 3ⁿ inclusive, i being an integer between 0 and (n - 1) inclusive.

Define f₁ as:
f₁(x, 0) = x [for 0 ≤ x < 3]

Define f_{(n + 1)} as:

• For 0 ≤ x ≤ 3ⁿ:
  • For 0 ≤ i < n:
    f_{(n + 1)}(x, i) = f_n(x, i)
  • For i = n:
    f_{(n + 1)}(x, i) = (x mod 2))
• For 3ⁿ < x ≤ (2 * 3ⁿ):
  • For 0 ≤ i < n:
    f_{(n + 1)}(x, i) = (3 - f_n(x, i))
  • For i = n:
    f_{(n + 1)}(x, i) = (2 - (x mod 2))
• For (2 * 3ⁿ) < x ≤ 3^{(n + 1)}:
  • For 0 ≤ i < n:
    f_{(n + 1)}(x, i) = (3 - f_n(x, i))
  • For i = n:
    f_{(n + 1)}(x, i) = (2 + (x mod 2))

f₂(x, i) is the coordinate along the ith axis for the endpoint of segment number x in the first step of the 2-D Peano monster curve:

       i
 f2   0 1

  0   0 0
  1   1 1
  2   2 0
  3   3 1
x 4   2 2
  5   1 1
  6   0 2
  7   1 3
  8   2 2
  9   3 3

f₃(x, i) is the coordinate along the ith axis for the endpoint of segment number x in the first step of the 3-D Peano monster curve:

         i
  f3   0 1 2

   0   0 0 0
   1   1 1 1
   2   2 0 0
   3   3 1 1
   4   2 2 0
   5   1 1 1
   6   0 2 0
   7   1 3 1
   8   2 2 0
   9   3 3 1
  10   2 2 2
  11   1 3 1
  12   0 2 2
x 13   1 1 1
  14   2 2 2
  15   3 1 1
  16   2 0 2
  17   1 1 1
  18   0 0 2
  19   1 1 3
  20   2 0 2
  21   3 1 3
  22   2 2 2
  23   1 1 3
  24   0 2 2
  25   1 3 3
  26   2 2 2
  27   3 3 3

and so on, up to as many dimensions as you wish.

The procedure could be generalised in a different way, instead of slicing into 9 sections each 1/3 the original length to cover 2-D, the curve could be sliced into 25 sections each 1/5 the original length, or into 49 sections 1/7th the length, or oⁿ sections 1/o the length for any odd o greater than 1, and any n number of dimensions.