A spacefilling curve
is a parameterized function which maps a unit line segment to a
continuous curve in the unit square, cube, hypercube, etc, which gets
arbitrarily close to a given point in the unit cube as the parameter
increases.
Spacefilling curves serve as a counterexample to lessthanrigorous
notions of dimension.
In addition to their mathematical importance, spacefilling curves
have applications to
dimension reduction,
mathematical programming [Butz 1968],
multidimensional database indexing [Lawder 2000], and
radiofrequency electronics [Zhu 2003].
The spacefilling constructions are usually designed to map between
the real unit line segment and the unit ncube. My interest is
to expand their range to the entirety of nspace.
The Algorithm
In Space filling curves and
mathematical programming Butz gives an algorithm for
computing the Peano spacefilling curve in terms of the base3
representation of coordinates between 1 and 0. The grid shown to the
right has m columns of (rank) n digits, each row
corresponding to one spatial coordinate. The leftmost digits are the
most significant, the ternarypoint lying to their left.
Digit i of row j, p_{j}^{i},
is replaced by 2p_{j}^{i}
if the integer sum of:
 all the digits in columns left of column j which are not in
row i and
 the digits in column j above row i
is odd.
The area around digits contributing to this sum for the circled
p_{3}^{3}
is shaded in the figure.
Notice that the parity (zero vs. nonzero) of digit
p_{j}^{i}
remains unchanged when it is replaced by
2p_{j}^{i}.
Thus the order of processing digits is arbitrary.
This peanoflip!
operation is its own inverse.
A naive implementation would take time
O(mn^{2}) for the complete table.
By scanning down each column from left to right while calculating the
total parity and the parity for the portion of each row already
visited, this can be reduced to O(mn).
Here is the simplest case. Groups of flipped digits are underlined.
scalar
 0
 1
 2
 3
 4
 5
 6
 7
 8


digits











flipped











So within a 3*3 cell an odd higher digit flips the lower digit,
creating the signature S curve.
scalar
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27


digits





















flipped





















From 0 to 8 we have seen digits increment or decrement only by 1.
From 8 to 9, 17 to 18, and 26 to 27 the low order digit jumps from 2
to 0 while carrying into the digit to its left.
The Curve
What results is a curve with a high degree of selfsimilarity. Each
square is composed of 9 squares; 5 of which connect bottom left to top
right and 4 of which connect bottom right to top left.
The horizontal segments in the curve at right are all the same length.
Vertical segments, however, are two and five times the horizontal
length.
Long straight segments degrade the closenesspreserving properties
important to many applications. Where a linear distance of 5 units
may map to an nspace distance of 5 in this curve, in a
wigglier curve it would always map to a shorter distance.
This suggests that a figureofmerit for spacefilling curves would be
to sum, for every pair of mdigit points in nspace, the
ratio of the euclidean distance to its corresponding linear distance.
The Performance of SpaceFilling Curves
for Dimension Reduction reports the results of such measurements.
Wigglier
Each 2dimensional cell connecting either bottomlefttotopright or
bottomrighttotopleft suggests a method for making the curve
wigglier: swap x and y coordinates for all the
bottomlefttotopright cells.
Generalizing this to higher ranks is not straightforward. Each
3dimensional cell connects along one of three diagonals of the cube.
Centering
The transforms outlined above can be easily generalized to cover
nonnegative coordinates of arbitrary size by moving the ternarypoint
to the right. Furthermore, the precision to calculate and
ternarypoint position can be determined when the function is called
based on the magnitude of its arguments.
Also useful would be a spacefilling curve covering all integer
coordinates, Z^{n}. Although each
3^{mn} point curve is symmetrical
around its center, the coordinates calculated by the algorithm given
above are nonnegative. Although the conversion from the digit table
to nspace coordinates could subtract one from each digit;
because the number of digits is autoscaled, discontinuities result
at 3^{mn} boundaries.
More fundamental is that, if all of nspace is to be covered by
a doubleended selfsimilar curve, then negative linear numbers must
paint half of it. Thus the positive half of linear numbers in the
range 3^{mn}/2 to 3^{mn}/2 must paint a shape other than a
square. Fortunately, they form what could be described as a
rectilinear spiral:
The algorithm to convert from an integer scalar to
n centered Peano coordinates is:
 Find the smallest m such that
9^{mn}/2 is greater or equal to
absolutevalue of scalar;
 Convert scalar + 9^{mn}/2
into a ternary digit array;
peanoflip!
the ternay digit array;
 extract each coordinate from its array row; offsetting it by
9^{m}/2.
The algorithm to convert from n centered Peano coordinates to
an integer scalar is:
 Find the smallest m such that
9^{m}/2 is greater or equal to
the absolutevalue of each the input coordinate.
 Convert the coordinates offset by
+9^{m}/2
into a ternary digit array;
peanoflip!
the ternay digit array;
 extract the scalar from the array; offsetting it by
9^{mn}/2.
The divisions all round toward zero. The base of the exponents is 9
rather than 3 because, although the center square of the
3^{m} scale
cube has the same orientation as the corner squares, it is traversed
in the reverse direction.
Praxis
slib/peanosfc.scm
is a Scheme implementation of Peano conversions between integer
scalars and integer coordinate vectors of arbitrary size.
 Function: natural>peanocoordinates scalar rank

Returns a list of rank nonnegative integer coordinates corresponding
to exact nonnegative integer scalar. The lists returned by natural>peanocoordinates
for scalar
arguments 0 and 1 will differ in the first element.
 Function: peanocoordinates>natural coords

Returns an exact nonnegative integer corresponding to coords, a list of
nonnegative integer coordinates.
 Function: integer>peanocoordinates scalar rank

Returns a list of rank integer coordinates corresponding to exact
integer scalar. The lists returned by integer>peanocoordinates
for scalar arguments 0 and 1 will
differ in the first element.
 Function: peanocoordinates>integer coords

Returns an exact integer corresponding to coords, a list of integer
coordinates.
Further Work
 Develop a "wigglier" variant of the Peano curve.
The Peano curve described here does not have the isotropy property
called for by Multidimensional
SpaceFilling Curves:
the lengths of axisaligned projections of the spacefilling curve
should be equal.
The Peano curve reflects cells in order to make them contiguous,
but does not perform the rotation causing such vexation in
Recursive Formulation of Multidimensional
SpaceFilling Functions
It should be possible to rotate those cells currently subject to
an odd number of reflections. That would rotate 4 of the 9
subcells of each cell.
 Write comparison functions for Peano fixedpoint coordinates.
 Write comparison functions for Peano floatingpoint coordinates.
 Use these functions to extend the WB
Btrees to multidimensional indexes a la
[Lawder 2000].
Copyright © 2005, 2006 Aubrey Jaffer
I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.
My actions and comments do not reflect in any way on MIT.

  SpaceFilling Curves

 agj @ alum.mit.edu
 Go Figure!
