display | more...

This might do your head in

Imagine that you have a square of paper and a black pen which draws lines with no width. Is it possible to draw a curve on the paper which leaves it entirely black?
I've recently asked this question to several people - who had differing degrees of mathematical aptitude - and each of them has told me that it is impossible. Perhaps you would too; and indeed quite recently I tried to prove something assuming such a task to be impossible, only to be told that it can be done.

Here's how

Formally speaking we're looking to construct a surjective mapping from [ 0,1 ] to [ 0,1 ]2 (a curve is really just a function from a subinterval of R to some space, and surjectivity requires that its track should fill up all of that space). I'll define the curve as the limit of an infinite sequence of curves; the first one looks like this:

     .;------------;------;;;;;;;;;;;;;;,,,,,,,,,,,,,,,...,.....,.................,,...... .....                                                      
   +xXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXXXXXXXXXXXXXXXXxXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXxXXXX#####Xxx+==-   
 .X#+===+x+xxxxxxxxxxx+x+xxxxxxxxxxxxxxxxxxxxxxxxx+xxx+x+xxxxxx++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++====++xX.  
   +=-==-;---------------------------------===---==-=-======================================================+++++++++++++++++++++++++++++++-+=-=-=+.  
   x=-=-                                                                                                                                    x=---=+.  
   #=-==.                                                                                                                                   x=---=+.  
   x=-==.                                                                                                                                  .#=---=+.  
   #=-==.                                                                                                                                  ,#----=+   
   #====.                                                                                                                                  ;#----=+.  
   X====.                                                                                                                                   #=--=+=   
   #-===.                                                                                                                                   #=--==;   
   -,===.                                                                                                                                   x=--==,   
   #-===.                                                                                                                                  ;#+=-==,   
   #====.                                                                                                                                  x#=--==,   
   x=-==.                                                                                                                                   X=--==,   
   X=-==.                                                                                                                                   #x--==,   
   x+-==.                                                                                                                                    X--==,   
   -+-==.                                                                                                                                    X--==,   
   ;x==+.                                                                                                                                   +#=-==,   
   ;x-=+                                                                                                                                     x--==,   
   ;x-=x                                                                                                                                    -#====,   
   -x-=x                                                                                                                                     X=-==,   
   ;x-==                                                                                                                                     -+-==,   
   =x-==                                                                                                                                     ++-==,   
   -x-=x                                                                                                                                     =x-=+,   
   .+==+                                                                                                                                     -x-=x;   
   .x==+.                                                                                                                                    .x==+.   
   .x==x.                                                                                                                                     +==+=   
   .x==X,                                                                                                                                     +=-=#   
   .x==+.                                                                                                                                     x=-=#   
   .+===                                                                                                                                      x=-=#   
   .+==x-                                                                                                                                     x=-=x   
   .==-+=                                                                                                                                     x=-++   
   .==-++                                                                                                                                     +=-+=   
   .==-++                                                                                                                                     ==-=X   
   .==-+-                                                                                                                                     =+-=#   
   .==-++                                                                                                                                     =+-=#   
   .==-++                                                                                                                                     =+--#   
   ,==-+=                                                                                                                                     ==--#   
   ,==-+=                                                                                                                                     +=-=#   
   ,==-=x                                                                                                                                     x=-=#   
   ,==-=#                                                                                                                                     x=-=X   
   ,==-=X                                                                                                                                     x=-=#   
   ,==-=X                                                                                                                                     x=-=#   
   ,==-=x                                                                                                                                    .x--+=   
   ,==--x+                                                                                                                                   =x--+=   
   ,==--+X                                                          -##=                                                                     =x--x,   
   .==-=xX                                                          ####+                                                                    ++--x,   
   ,==-=+                                                            =#####                                                                  X+--x,   
   ,==-=X                                                               #####                                                                #=--x,   
   ,==-=x                                                                 X####                                                              x=--+.   
   ,==-=xx                                                         .       ;##########x-;,...                                                #=-=+.   
   ,==-=x=                                             .-############################################,                                       X=-=+,   
   ,==--x.                                       -+###############+-.    -x#####; .         x++###########;                                  x+-=+.   
   .==-=#                                 ;############-              ;#####=                        +#########=                             x+--x,   
   ,==-=-                         ,x############x;                 .######                                -#########                         ++-=x,   
   .==-=x.                  ;###########xX                        ######                                        #######x                     X=-=x,   
   ,==-=+#               .######X                               #####                                              ;######-                  #=-=x.   
   ;++--=+             =####X                                   ####                                                  =#####x                #=-=x;   
    -+====           #####                                                                                               +######             X=--+.   
     ,=-=X        =####-                                                                                                    ######           x=--x-   
     ,===X     ,#####.                                                                                                        -######        X=--x-   
     ,+==+   #####x                                                                                                             .######     .#=--x,   
     ;+=--,####X.                                                                                                                  ######    X=--x;   
     ,+=;+###x                                                                                                                      ;#####.  =+--+-   
     ,+=-##=                                                                                                                          =##### .+--+x   
     ;+=;,;;-X###################x==+x+==,... .     ..    .....        .   ..,....    x-.,..    .  . .                                  -x###-=--=+   
     ;x+==-==+=====-----------==+xxxxxxxxX##############################X###X#XXX####XxxXXX###XX##X#XXXXXXXXXXXXXxxxxxxxxxxxxxxxxxxxxx+-,..,;----=x   
     .=xxXXXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXXXXXXxXxxxxXXXXxXXXXXXX#XXX#XXXXXXxX##X#X#XX##XXX####X####X##XXxxxxxx+++++++++++++++++++++++=========+#,
I've drawn a curved line here between the bottom left and bottom right hand corners: its should really be a straight line, but I've drawn it curved for reasons that will become clear when I've drawn the next picture. The second curve looks like this:

      =x+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=++++++=======================++-    
      -=====++=++++++++++++=--========--=======-=======+++xxxxxxxxxxxx+=---==+++xxxxx+xxxxx+++++++xxxxx+=----+xXXX#XXXxX##XXXXXXxxxxXxx+=--=--====    
      ;==++x+xXX++++===+x++x#######+###################++=---;,;-;;;;;,#=-=x-==+=;;;+===;;==++=x#x,-=, .X=--=+             .,,,,,,,.,,+;x+==,=-===    
      -==X                                                             -+-+-                            X+--=#                             +,=-==+   
      -==#                                                             ;x-+,                            +x--=#                             =,---=+   
     .===#                                                             -X-++                            =#--+=                              --=-=+   
     ;===#                                                             -x-+#                             #=-+=          ###                 ;;=-=+   
    .-===-                                                             -X-==           ,                 #+-+-          #####               ===-=+   
    ;====X                                                              #-==          #####+             X+-+X            ,###+              ---=+   
    ===--#,                                                             #-=#;           ,#####;          xx-=X          =;-+#####x          =-=-=+   
    ===--#                                                              #=-#         =;   X#####         -x--X-     =################       ----=+   
    -==--#                                                              x=-X   .###################,      x--X-    #####       ########-    -----+   
    ===--#                                                              x=-=;=######;      =##########X- ,=--x.  ####x       ####X  x####   =---=+   
    ;-==-#                                                              #=.;####x        +####     =######-.;+  ####        ###X      ,###x;---===   
     ;==-X                                                              +;,###          ####          x####=   ###-       ###           ###+,.;==-    
    .-=--X#                                                             #,###       ..  .                x########+X######=              X###=,-=-    
    .-==-x;                                                             #,########XXxxx+=-=xXXxX#X##xxxx=. ,X##=.,-=+=++++=+xX##########+,=###;-==    
    .-==-x-                                                             #;.+#####x--x#############X#####XXx=.  ;=+++XXX++X#########x+; ;-####+,-=+    
    .-==-X-                                                             #-=.   +###+                       ;=-=X                     ;X######=--=-    
    .-==-X                                                              #-=-     ####                      =+-=#                     ####.   +--==    
    .-==-x                                                              #-+-       ###+                    =x-=#+                  #####     x-==-   
    .-==-+#                                                             #-=#        ###                    ,x-=#                  ####x     .x-==-    
    .-==-=#                                                             #-=x        ###                     x--#                  ###=   #  =x-==-    
    .-==-=x                                                             x=++         ###;                   #--#           ##.    ###  ###  X+-==-    
    .-=--xX                        +####.                               ++=+       ########+                #--#X          ####-  ##. ###   +=-==-    
    .-==-+                         ,#######.                            ;x+=      ###############,          #--#             x##########,   +=-==-    
    .-==-+#                           .x######                          .x=-    ##### ##+ ,X#######.        #--#               +#######.    +=-==-    
    .-=--=#.                         ..,;x######=;.                     .X=x- X####,  ###      ,--         +X--#                 .###X      .--==-    
    .-==-=#                 ;x###########################-              .x-x  ###x   ;##.                  -#--#.                 ###.      X=-==-    
    .-==-=#         .x##############X=   #####X###############x;        .X-X+       X###                    #--#.                  ###=     x--==-    
    .-===-#      ###########x,          ####X          ,###########x.    x-x      ####=                     #--X+                  -###-    x--==-    
    .-==;=+.  -########-              #####=   .            -##########  =-+    ####-                       #--x.                   +####   +=-==-    
    .-=-;;,-#######,                 ####;                        -######   X#####=                        -#--x-                     ####++,--==-    
    .-=--+######=                                                   .+#########=                   ,  .,;; =x=-+-..#   ,.x+,xxxxx,,,   +#####;;==.    
    .-==--###x.. .-+xxxxxxxxxXXXX####Xxx+++=-==+x##############XXxx+-.  .;x+;  ;+x########################Xx+--=xXxX####XXXXxxxxxXXXXx=,  ;##+;=-     
    .-==,;X##=.x###############xxxX##x- .=######- .X#####X############Xx+=-.,-+X#################X####XXXXXX####X###XXXXxx##XXXX#####X=..=###x--;     
    .-==-;-###                        -#####=.####                    ;,==x--+=                                                        ####x=--==,    
    .-==;=--###,              ####+  ####. ,=   ####X                     #--x=                                                       ###-   =-=+=    
    .-==;-+- x####-         ###X   x####=;-+;    ;####                    #=-x+                                                      ###=   X+-==-    
    .-==;=x     ######+,=#####. ;#####  -=-x;      ###x                   X=-x=                                                     ###;    #=-==-    
    .-==-=x,      ,################X    ++-x;       ###                   #=-X=                                                    ####     #=-==-    
    .-==;=+#+           =######,        +x-x-       ###                   ==-X                                                    ###=      #+-==-    
    .-==,=+#    .           .###;        X-+.       ####+                 #+-#                                                    ###       -x--=-    
    .-==,==#=                 X###X     .#-+-     x########=              ==-#                                                   ###X       ,X--+-    
    .-==;=+#=                   ###x    -#-+#   ####### -####.            #=-X,                                                 +###        ,X--+=    
    .-==;==x-                            +==X  ###  ###    ###            #--X,                                                 ###+        -#--++    
    .-==;==X=                            ++=+  ##   ###                   #--x.                                                =###          X=-=-    
    .-==;==#=                            +==+      x###                   #=-+x                                                ###x      ##  x+-+-    
    .-==-==X                             X+=#      ###                    #=-=#                                         ###    ###     ####  ,+-=+    
    .-==;==x#                            -+-x    .###,                    x=-=X                                         ####X  ###   #####   =+-=#.   
    .-==--++#                            x+-x   ####                      #=-=X                                           ####=##x  ####X    =+-=+    
    .===---=#                            ==-==#####                      .X--=#                                            ;#####+ ####.     -+==x    
    ,++----=+xx#######################X##+--;####-,x###################Xx++---#                                              ########        ;+-=x.   
    ,++==----=+xxXX###############XXX###x+=-.-##X  -+XXXXX##XX##XXXXX###Xx=---##                                               ######        -x--X=   
     .===--=+x++;;                 ;,-  ,-+--X####=; .  ;.  ;,  ,,,,,  ..,X=-=X                                                ####X         -+--x=   
      .==-==x,                            +--- -####                      #--=x                                                ;###          -+--x=   
      ,==--=X=                           .x==#   .###;                    #=-+x                                                 ###+         -+-=x=   
      ,==-,=+#                            x=-#;    ####                   #=-+;                                                 ####         ;+--=    
      ,==--=x#                            +=-X#     ####                  #--++                                                  ###         -+--+X   
      ,==--=+-                            +=-x       ###-                 #=-++                                                  ####        -+--=#   
      ,==-,=++                            +=-x#       ###                 #=-+=                                                  ####        -+--=#   
      ;==-,=x#                            ==-x#     x####=                #--+=                                                  x###.       -+--=#   
      ,==-;=+#                            =+=X=    ########.              #=-=#                                                   ####       -==-=#.  
      ,==-;=+#            ###X            =+=+   x###########            ,#=-=#                                                   x####      -+=-=#.  
      ,==-;=+#             ####           =+=x   ###  X##+#####=         .#=-=X                                                    ####      -+--=#   
      ,==-,=+#              ####          =+=x x###   ###   -x#x          #--++                                                     ####     -+=-=#;  
      ,==-,=x#              =X###;        =+-x ##     ###+                #=-+-                                                      ####    -+--=#   
      ;==-;==#         .##############X   ;=-X+      ###-                 #=-=#                                                       #####  ;+--=X   
      ,==--=+#     ######## -X############=,;x-     =###                 +#=--#                                                        ##### .+--=#;  
      ,==--=+++x######     x####;     =####,.+,    ####x                 .x=--#.                                                        x###  =--=#   
      ,==--==######       ###           X###  ;  +####-== ..==##X--=#####Xx+==x=;-===+=x###x##################xX###+=====-x############x+X###x=--=#-  
      ,==---;,+x;  ,=x++=.      .xXXXXx-.x##########= ,-+xXXx++=+xx++===------==+xxxxx++==++===-=============+++==++xxxxxx+=============;..,;-----;   
      ;==----;..,;-===+++x+xX###Xx+++++=-,  -xXXX+;.,-==========================================================================================+xX=  
      ;+x+=+-==xX########XXxxxxXxxxxxxxxxxx+xx++==++xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx+=;
The lines are drawn cruved here so as you can tell which boxes they belong to. Note that the second curve is made up of ten smaller copies of the first (and it's three times longer). So, to construct the third curve, just replace each of these copies of the first curve with suitably scaled down and rotated copies of the second. Thus the third curve is composed of one hundred copies of the first curve...
To complete the rest of the sequence, just keep repeating this process (it is called fractal iteration). I claim that this sequence of curves (name them, say, fn: [ 0,1 ] -> [ 0,1 ]2)converges to a fractal curve (say, f: [ 0,1 ] -> [ 0,1 ]2) which passes through every point in the square. Such a curve is known as a Peano (monster) curve.
In terms of justification, I could launch into some dreadful epsilon/delta argument that would send you all to sleep, but there is a nicer way for this particular curve.

Here's why

Suppose you have some number in the interval [ 0,1 ] - it can be written in the form of a decimal expansion of the form 0.d1d2d3... (n.b. 1=0.999...) where each di is one of 0,1,...,9. Now have a look at the following picture:
#################
#       # 6 # 7 #
#   4   #########
#       # 5 # 8 #
#################
# 3 # 2 #       #
#########   9   #
# 0 # 1 #       #
#################
Note that this picture numbers the boxes in the same order as the curve passes through them in the second picture. Ah ha! This then allows you to work out approximately where any given number in the interval [ 0,1 ] gets sent to one the second curve - it gets sent to the box labeled by d1, the first digit. You can then more accurately determine where the number gets sent to one the third curve by subdividing box d1 into ten parts again, and of these you know that the image point must lie in box d2. If you keep repeating this process, you can determine where a given number get sent to one sucessively finer iterations of the curve to a greater degree of accuracy; because as each time the process is repeated, the boxes get at least four times smaller.
I'm afraid I couldn't make that last sentence any shorter. How about a quick example: suppose the number in question is pi/10 = 0.31415... Dissect you square into ten parts as prescribed above, and you know that pi/10 must be mapped into box 3. So, subdivide box 3 into ten parts, and you then know that pi/10 belongs in sub-box 1. Subsubdivide sub box 1, etc. Now to prove the convergence of the curves. By the above algorithm, we know that from some 0 <= a <= 1:
  • we can place f2(a) inside some box of size at most one quarter
  • we can place f3(a) inside some box of size at most one sixteenth
  • we can place f4(a) inside some box of size at most one sixty-fourth
and so forth. In general, fn(a) is bounded by some box of area (1/4)n-1, so for any value of a, (fn) is a Cauchy sequence. Because [ 0,1 ]2 is complete, all the series converge and so the limiting monster curve f exists. Finally, it should now be clear that f is surjective as claimed: by using the repeated subdivision process described above, you can produce a decimal series corresponding to any point in the square. As a techincality, consider the subdivided boxes as open sets ie. not inculding their boundaries. If you want to find the decimal series for a point on a boundary between two boxes, just take numbers corresponding to boxes on either side of the boundary as you 'zoom' closer in; the resultant decimal series must then converge to the boundary.

m-m-m-MONSTER KILL kill kill*

You might not believe this argument at first, as it seems to go against your previous conceptions on what the real numbers were. Initially you might wish to dismiss this as a pathological example of no relevence to the world as described by real numbers, but Mandelbrot would argue otherwise. In his book on the fractal geometry of nature, he writes "[ when ] Peano curves are observed attentively, letting one's thoughts wander about, it becomes very difficult not to associate them with the diverse aspects of Nature.", citing the drainage basin of river as an example. The madness doe eventually stop, you'll be pleased to hear, as for a!=b Ra is not homeomorphic to Rb, so toplogically speaking at least there are no more surprises. Proof: Ra - some point and Ra - some point have different homology groups.

Remarks

  • The fractal dimension of this curve is 2, which seem fairly sensible given that it fills an area; indeed the existence of such curves is a motivation for the definition of the fractal dimension of a curve. Fractal curves which behave in a similar way but don't manage to fill and area (such as the Koch curve) can then be sensibly expected to have fractal dimensions between 1 and 2.
  • The generator for the curve I describe above is more complicated that in needs to be - I devised this one because it lends itself nicely to decimal expansions. Here's a simpler one:
    
       XxX#XXXXX############X############XXXX##XX####X#####X##X###########XXXXXXXXXXXXXXXXX#X#X#X##X###X###XXXXXXXXXXXx#X;  
       #x==+xXXXX#XXXXXXXXXXXXXXXXXXXXXX#XXX#X###X##XXXXXXXXXXXXXXXXXXXXX##X#########X#X##X##X###XXXXXXXXX#XXXxxx++-,.,=x;  
       .+-=-                                                                                                        x#--+,  
       ,x=+;                                                                                                        ##+;+,  
       .x=+=                                                                                                       ###;;x,  
       .+==-                                                                                                     =###-,-x,  
       ,+===                                                                                                  =##### ---x,  
       ,+===                                                                                                 #####-  x=-+,  
       ,+==-                                                                                                #####    #+-x,  
       ,+===                                                                                              =####      =+-x-  
       ,+===                                                                                            .#####       ;x-x;  
       ,+===                                                                                          -####-         .x-+-  
       ,+===                                                                                        X####.           .x-+-  
       ,+=-=                                                                                      #####;             .x=+=  
       ,+===                                                                                    #####+                x=+-  
       ,+===                                                                                 -#####;                  x=+=  
       ,+==+                                                                                #####,                    x=+-  
       ,+==-                                                                              ####;                      .x=+-  
       ,+==,                                                                            ####                          +=++  
       ,+===                                                                         -###X                           .x=+x  
       ,+===                                                                       ;###x                             .x=+=  
       ,+===                                                                     +###=                               .x=+-  
       ,+===                                                                   X###=                                 .X=x-  
       ,+===                                                                 ####                                    .x=+-  
       ,+===                                                              =####                                      .x=x-  
       ,+===                                                            X####                                        .x=x;  
       ,+==-                                                      -X######.                                          .x=x,  
       ,+===                                            x#X############-                                             .x=x,  
       ,+===                                            +######x######                                               ,x-x;  
       ,+===                                                   ###=##                                                =x-x,  
       ,+===                                                 #### ,##                                                ;x-x,  
       ,+===                                               ####   ###                                                ;x-x;  
       ,+===                                            ,####.    ###                                                ;x-x,  
       ,+===                                          -###+       ###                                                -x-x,  
       ,+===                                        ####x         ###,                                               .x-x,  
       ,+===                                     +####.                                                              ,x-x,  
       ,+==x                                   ####x                                                                 ;x=+,  
       ,+==#                                 ####+                                                                   =+=+,  
       .+==#                               =###-                                                                     -+=x,  
       ,+==x                             x###X                                                                       ;+=+,  
       ,+=++                           ####+                                                                         ++=x,  
       .+=+-                         ####;                                                                           ,+=+,  
       ,+=+=                       ####.                                                                             =+=+,  
       .x=+=                     ####                                                                                x+=+,  
       .x-+=                   ####                                                                                  ++=+,  
       ,x-x;                -####                                                                                    ++=+,  
       ,x-x,              ;####                                                                                      ++=+,  
       ;x-x,            =###x                                                                                        x+=+,  
       ;x=+.         =####;                                                                                          ++=+,  
       -x=x,       x####                                                                                             ++=+,  
       =+=+,     =###                                                                                                ;x=+,  
       x+=+.  .####-                                                                                                 -+=+,  
       X=-;. ####=                                                                                                   x+=+,  
       #=-=####.                                                                                                     x+=+,  
      .X--;X-                                                                                                        ;+=+,  
      ,x----. .,;-;-Xx+xXX+xX+=xxx#####################X+XXx+++-;;,..... .,, ..,.               .                    ,+=+;  
     .#x==++X#######XXXxxxxXXXXXXxxxxxxx+++++++++++++xxxxXxXXXX###########################XXXXXxxxxxxxxxxxxxxxxxxxxxx++xX;  
      -#xxx+---==================================================+++===+++++++++++xxxXXxX########################XXXXX+,
    
    is the first curve of the sequence, and
    
          ..               ...                                                                                              
        ;#XXX###########################x+=-;;;,,,;=x########################XXXX###########################Xxxxx+=+xX#x,   
        -x==+=+++++++++++++++++++++++-   ,+########=  -+++++++++++++++++++++==+===++++++++++++++++++++++++; ,;;;.+##-=++.   
        ;+==x                          #####x   ;+x##;                        x==                          =#######;;===.   
        ;+=-X                       =####;     ;-=  ###        .              X=x                        x######  X-,===.   
        ;+==#                     ;####        =+x    ###    ;###            .X=x                      x#####     #+.;+=    
        ;+==X                    ####-         x+#.    ####   ##             .X=x                     ####.       #+-;+=    
        ;+=-#                 .####            ++x       +##. ##+            .X=x                   ####          #X=-==    
        ;+==#       #####+   ####              =+X.        X####=            .X=x         ####+,  x###x           =X=-==    
        ;+-=X       ##########X                =+X,   ###########            .X=x          .-#######;             +X=-==    
        ;x-=+            =####                 =+X,   +x#=;.   X##=          .x=x             +####               +#=-==    
        ;+-+=          +### ##                 -+x,              ###         .X+x          =#######               x#=-==    
        ;+-+=         ###x  ##                 -+x;               X###        X++        =####  ###               xx--==    
        ;+-+-       ####    ##;                =+x;                 ###x      X+=     -####x    .##               #X--==    
        -x-+x     .###=     ###                -+x-                   ###     X++   -####,       ##               xx=-==    
        -x-x,    ####                          ,+xx                    ####.  X+=  ####;                          #X--==    
        ;x-+.  ####                            ,++=                     .###  =+; =###                            #x--==    
        ;+==-.###+                             ,++-                       ####;=  ###                             #x=-==    
        ;+=-;##=.=+X###########################x+=x+x+##+=----====--==--- .=##==- ###   ........................ .x+=-==    
        ;+=;-##. =+xxxxx+++x++++++xxxxx+++x++==+++x###################X=;.,###.-++###-+###########################+=--==    
        ;+=-,###                                ++                    ,+####  -=+  ###=    ,,,,.====+++==--...... =#=-==    
        ;+=-,####.                             ,+X.                   ###-   -+=+   X###.                          #=-==    
        ;+==-.####-                            .+X.                 ####     +++x     ####                         #=-==    
        ;+===  ####                            ,+X,      .-       ####       ++++      #####                      =#--==    
        ;+==X   ###x                           .+X.      ###   .####         ++++         x###-                   .#--==    
        ;+==x;   =###                          ,+X,      .##  x###           ++++           ############+          #=-==    
        ;+==x-     ###                         .+x,       ######;            ++++            =###;   +X.           #+-==    
        ;+==x,      ###=                       .+X-       =###               ++++             #####                xx-==    
        ;+==x        ;###;                      +x-      ;###  X####=        ++++             ### ###,             #x-+-    
        ;+==x+         ############x           .+x;     ;########x+          ++++             ###   ####           #+-+-    
        ;+-=x+         ######,    =;           .xX;     ####                 ++++             ###     ###+         #+-+-    
        ;+-=x          ###  ####x               +X;   -####                  x=++             -#       -##x        #=-+-    
        ;+-=x.         ###    ;#####            +X;   ###                    +=++                       ,###       #+-+-    
        ;+==+X         ###        -####         ++  ####                     x=++                         ###,     #=-+-    
        ;+-==#                       ####.      x=+##X                       x=+=                           ###    #=-+=    
        ;+--=#                         ####.    +-=##                        x=++                           =##-   #=-=+.   
        ;+--=#.                          x###   +;=#x                        +=+-                           =###=x##+-==.   
        ;+--=X                             ###. =-;##                        ===+;;+###x+###################-;+##-+x=-==    
        ;+--=+-,;,;;;---=++xx+=---==--=+#=  =##.== ##=X#######################+=+##x=X+=-=-+;+,,,,;,,.,.,.,,,,X#x ,x+-==    
        ;+====X##########################X- ###==+ ###                        +==.                           ###  .#+-==.   
        ;+--xx-                           -###- ++  ###                       x=+;                          ###-   #+-==.   
        ;+-;xx                           ####. .xx   =###                     X=x-                         ###     #+-==.   
        ;+=-+#                         ####x   ;xx     ###                    #=x;                       ,###      Xx-==.   
        ;+--+X                        ####     ;xx      ;###  =##             X=x;                      ,###       ##-==.   
        ;+--xX                      +###+      -xx        -##-x##-            X=+;                     ####        -#-==    
        ;+--xX                    .####=       ;xx          ######            X=+;                   -###          -#-=+    
        ;+--+X                   +###X         ;xx            ####            X=+x                 .###x           .#-==    
        -+--xX                +####-           ;xx.            x##-           X==;       -#=;.   .####             .#-==    
       .x=--+X          ###########            ,xx.      ##########=          X=+#      ############                #-==    
       .+=--+X          ##,  ######            ;xx               ####         x=+=            -#####                #-=+.   
       .+=--+X             ###  ###            ,xx.               ####-       #=+;           x###;##               .#-==    
       .+=--xX          -###    ###            .xx.                 ####      #=+;         -###x  ##                #-==    
       .+=--x,       x####x     ###            .xx.                   .###,   #=x;       x####   .##                #-==    
       .+=--x,     #####-                      .xx.                     x###  x=+;      ###.     ###                #-=+    
       .+=--x     +###,                        ,+X.                       ### ,;=.    ####=       ##                #==+.   
       ,+=--+x   =##.                          .+X,                        ,##x   +#####,                           #===.   
       .x=---+x####                             =+                           #########                              #+==,   
        =+--+####=;,x##X##################X+===+++x####xX###+++++;.,..         ,+X=                                 .+==.   
        -x++-;..,-=+++++++=+===========++++xXxx++=+===++++++xxxxXX###########x=;,.;=+X####XXXX#XXXXxxxxxxxxxxxxxxxx+==-==   
        ,-==++xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXxxXX##############################XXx++++++xxxxxxXXXX##-  
                                                                                               .,.,,--+#####Xxx++++= -,..
    is the second.
  • Considering this simpler example, can you generalise it to a monster curve that fills up a volume?

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]2 is to again consider the decimal expansion (or binary expansion, or any base) 0.d1d2d3d4… and split it up into two numbers, 0.d1d3… with all the odd-positioned digits and 0.d2d4… 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]2 'planar' space. Similarly, [0, 1] can be mapped to [0, 1]3 by taking every third digit at a different 'phase' for each dimension, or [0, 1]4, or [0, 1]n 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, fn(x, i), n being a positive integer, x being an integer between 0 and 3n inclusive, i being an integer between 0 and (n - 1) inclusive.

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

Define f(n + 1) as:

  • For 0 ≤ x ≤ 3n:
    • For 0 ≤ i < n:
      f(n + 1)(x, i) = fn(x, i)
    • For i = n:
      f(n + 1)(x, i) = (x mod 2))
  • For 3n < x ≤ (2 * 3n):
    • For 0 ≤ i < n:
      f(n + 1)(x, i) = (3 - fn(x, i))
    • For i = n:
      f(n + 1)(x, i) = (2 - (x mod 2))
  • For (2 * 3n) < x ≤ 3(n + 1):
    • For 0 ≤ i < n:
      f(n + 1)(x, i) = (3 - fn(x, i))
    • For i = n:
      f(n + 1)(x, i) = (2 + (x mod 2))

f2(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

f3(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 on sections 1/o the length for any odd o greater than 1, and any n number of dimensions.

Log in or register to write something here or to contact authors.