rectangular spiral http://people.csail.mit.edu/jaffer/Geometry/PSFC

Peano Space-Filling Curves

A space-filling 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.

Space-filling curves serve as a counterexample to less-than-rigorous notions of dimension. In addition to their mathematical importance, space-filling curves have applications to dimension reduction, mathematical programming [Butz 1968], multi-dimensional database indexing [Lawder 2000], and radio-frequency electronics [Zhu 2003].

The space-filling constructions are usually designed to map between the real unit line segment and the unit n-cube. My interest is to expand their range to the entirety of n-space.

array of symbols representing digits

The Algorithm

In Space filling curves and mathematical programming Butz gives an algorithm for computing the Peano space-filling curve in terms of the base-3 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 ternary-point lying to their left.

Digit i of row j, pji, is replaced by 2-pji if the integer sum of:

is odd. The area around digits contributing to this sum for the circled p33 is shaded in the figure.

Notice that the parity (zero vs. nonzero) of digit pji remains unchanged when it is replaced by 2-pji. Thus the order of processing digits is arbitrary. This peano-flip! operation is its own inverse.

A naive implementation would take time O(mn2) 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
0
0
0
1
0
2
1
0
1
1
1
2
2
0
2
1
2
2
flipped
0
0
0
1
0
2
1
2
1
1
1
0
2
0
2
1
2
2
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
00
10
00
11
00
12
01
10
01
11
01
12
02
10
02
11
02
12
00
20
00
21
00
22
01
20
01
21
01
22
02
20
02
21
02
22
10
00
flipped
02
10
02
11
02
12
01
12
01
11
01
10
00
10
00
11
00
12
00
20
00
21
00
22
01
22
01
21
01
20
02
20
02
21
02
22
10
22
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.

Peano space filling curve overlaying 3-by-3 grid

The Curve

What results is a curve with a high degree of self-similarity. 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 closeness-preserving properties important to many applications. Where a linear distance of 5 units may map to an n-space distance of 5 in this curve, in a wigglier curve it would always map to a shorter distance.

This suggests that a figure-of-merit for space-filling curves would be to sum, for every pair of m-digit points in n-space, the ratio of the euclidean distance to its corresponding linear distance. The Performance of Space-Filling Curves for Dimension Reduction reports the results of such measurements.


Wigglier

Each 2-dimensional cell connecting either bottom-left-to-top-right or bottom-right-to-top-left suggests a method for making the curve wigglier: swap x and y coordinates for all the bottom-left-to-top-right cells.

Generalizing this to higher ranks is not straightforward. Each 3-dimensional 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 ternary-point to the right. Furthermore, the precision to calculate and ternary-point position can be determined when the function is called based on the magnitude of its arguments.

Also useful would be a space-filling curve covering all integer coordinates, Zn. Although each 3mn 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 n-space coordinates could subtract one from each digit; because the number of digits is autoscaled, discontinuities result at 3mn boundaries.

More fundamental is that, if all of n-space is to be covered by a double-ended self-similar curve, then negative linear numbers must paint half of it. Thus the positive half of linear numbers in the range -3mn/2 to 3mn/2 must paint a shape other than a square. Fortunately, they form what could be described as a rectilinear spiral:


rectangular spiral

The algorithm to convert from an integer scalar to n centered Peano coordinates is:

The algorithm to convert from n centered Peano coordinates to an integer scalar is:

The divisions all round toward zero. The base of the exponents is 9 rather than 3 because, although the center square of the 3m 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->peano-coordinates scalar rank

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

Function: peano-coordinates->natural coords

Returns an exact nonnegative integer corresponding to coords, a list of nonnegative integer coordinates.

Function: integer->peano-coordinates scalar rank

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

Function: peano-coordinates->integer coords

Returns an exact integer corresponding to coords, a list of integer coordinates.

Further Work


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.
Space-Filling Curves
agj @ alum.mit.edu
Go Figure!