space filling curve

Giuseppe Peano, born on 27th August 1858, was an Italian mathematician. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation ( in his first book dealing with mathematical logic, the modern symbols for the union and intersection of sets appeared for the first time.). The standard axiomatization of the natural numbers is named the Peano axioms in his honor. As part of this effort, he made key contributions to the modern rigorous and systematic treatment of the method of mathematical induction.

Moreover, Peano’s famous space-filling curve appeared in 1890 as a counterexample. He used it to show that a continuous curve cannot always be enclosed in an arbitrarily small region. This was an early example of what came to be known as a fractal.

He has done so many things ^_^ 

In the middle of the 19th century Riemann introduced his theory of integration. The last third of the century saw the arithmetization of analysis by Weierstrass, who thought that geometric reasoning was inherently misleading, and introduced the “epsilon-delta” definition of limit. Then, mathematicians started worrying that they were assuming the existence of a continuum of real numbers without proof. Dedekind then constructed the real numbers by Dedekind cuts, in which irrational numbers are formally defined, which serve to fill the “gaps” between rational numbers, thereby creating a complete set: the continuum of real numbers, which had already been developed by Simon Stevin in terms of decimal expansions. Around that time, the attempts to refine the theorems of Riemann integration led to the study of the “size” of the set of discontinuities of real functions.

Also, “monsters” (nowhere continuous functions, continuous but nowhere differentiable functions, space-filling curves) began to be investigated. In this context, Jordan developed his theory of measure, Cantor developed what is now called naive set theory, and Baire proved the Baire category theorem. In the early 20th century, calculus was formalized using an axiomatic set theory. Lebesgue solved the problem of measure, and Hilbert introduced Hilbert spaces to solve integral equations. The idea of normed vector space was in the air, and in the 1920s Banach created functional analysis.

Computer dimensions

How many dimensions is a picture on your computer’s screen? For example, this lovely Derain painting.

If computers, which store things as mathematical objects, can store this Derain painting, then mathematical terms like “dimension” might be useful to describe it.

On first glance, you might claim the number of dimensions is “two.” I mean, it is a flat picture, so shouldn’t it be two?

Well, I could make a case for 5 dimensions. Every point has 5 pieces of data attached to it, an x-coördinate, a y-coördinate, and then a value for red, green, and blue.

I should make a note about the colors. The human eye has realized that instead of looking for an infinite number of colors, it should just see how close a color is to three “focal colors.” Computers exploit this simplification, and only flash those three colors in different amounts to trick our eyes into seeing all the colors.

However, the computer doesn’t need to specify all amounts of each of those three colors, since our eyes can only distinguish a finite number of intensities of each of those colors.

This finiteness helps us a lot. I will assume each color is represented by a number 0-99 (numbers which make the math look nicer, rather than the usual 256), then the colors do not interfere with each other if we just instead make all green values bigger than blues, or say “green•100 + blue.” In fact, we can represent all of these colors with one number 0-999999.

Notice that this means that we only need one color dimension for our picture, instead of 3.

The spatial dimensions similarly compress to one, since there are a finite number of pixels.

So, I got to our original guess of 2, by compressing 5, but a completely different 2 than before.

We are not done yet.

Each location in space is attached to exactly 1 color, which makes a picture secretly a function from space on the screen to colors.

This can be turned into a function from integers to integers, as we have shown.

And with that function, each color can only go up to 999999, so by the same kind of finiteness as before, we can say “first spot’s color + 1,000,000•second spot’s color + etc.” This is a really big number, but we only need one integer to represent that whole maybe-5-dimensional picture.

In mathy terms, we are using 1 dimension to represent a function from 1 dimension to 1 dimension, which is representing a function from 2 dimensions to 3, which is a subset of 5 dimensional space.

In really mathy terms, a picture is actually a positive integer representing a 1-dimensional curve in 1-space, which is a space-filling curve for a 2-surface in 3-space.

That also means that a computer thinks of this:

as a single (really big) number.

To simplify things, here is is pixilated.

And here is the number that represents the pixilated picture, with colors 0-99:

684266804459885946705130835841985760844969
613976502568604052463645553454773455593375
524082393080551644650831572433684138372666
250946443474542557721229824434806843525364
551935823841632752731942915751958962786437
752628772419712539912726925542949181978255

(I was trying to color the number to make it easier to read, but could not figure out how)

On space-filling curves

Formal definition.

Let \(\phi :[0,1]\to T\) (where \( T\) is a topological space) be a continous function (i.e. \(\phi ^{-1}\) of any open set \( O\) of \( T\) is an open set of the unit interval) from the unit interval to a topological space. Such map is said to be an space-filling curve if \(\phi\) is onto (i.e. if \phi passes through every element of \( T\) ).

Note

Generally, space filling curves are represented on spaces homeomorphic to \( E^{n}\) euclidian spaces. So to say, the plane, or any geometric solid, since these are the easiest ways to visualize a space filling curve. The most popular example, perhaps, is the two-dimensional Hilbert curve.

Images

External image

A Hilbert curve from the unit interval to the unit cube

External image

Peano Curve from the unit interval to the unit cube.

External image

Flow Snake sapce filling curve.