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.