Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In discussion about the question Is there a way to represent the interior of a circle with a curve?, it was mentioned that such a curve cannot be one-to-one (because $[0,1]$ is not homeomorphic to $[0,1]^2$). I'm curious about in what way the Peano curve is not one-to-one.

The construction of the Peano curve is a recursive refinement of a particular path that discretely looks one-to-one, in that it touches every coordinate point at a given scale in a bijection. In the limit there's no bijection, but at every step there is a bijection between the curve so far and the coordinates of points within $[0,1]^2$ truncated to so many binary digits.

In a surjection that is not an injection, there must be some overlap (some $x,y$ where $x\neq y$ but $f(x)=f(y)$. What I'm getting at is...where is the overlap? I'm guessing it's not just at one point - is it at all points? how much overlap? What is the nature of the overlap (for a given point on $[0,1]^2$, which points in $[0,1]$ map to it?

(for discussion's sake, use the definition of the Hilbert-Peano curve)

Edit: A small bit of clarification: given a point $(j,k)$, is their overlap, and if so, how much (what is the cardinality of the inverse image at that point)? How about just for a particular point like $(1/2, 1/2)$?

share|improve this question
    
+1: Thank you for this question. I was actually wondering myself and then decided that I'm too stupid and that it is easy to see why it is not one-to-one... –  Fabian Mar 29 '11 at 15:16
2  
The self-similarity of the curve at least shows that the noninjective points are dense (either in the interval or the square.) –  Grumpy Parsnip Mar 29 '11 at 15:18

3 Answers 3

up vote 10 down vote accepted

The points of overlap are precisely those where one at least one coordinate is a dyadic rational $n/2^N$ for some integers $n,N$, except some points on the boundary of the square $[0,1]^2$. If you focus on the middle point $(1/2,1/2)$ of the square in the animation on the Wikipedia page, you can observe that it is approached from three different directions. (Actually, $H(1/6)=H(1/2)=H(5/6)=(1/2,1/2)$, where $H:[0,1]\to[0,1]^2$ is the Hilbert curve.) The same goes for the points $(1/4,1/4), (3/4,1/4), (3/4,1/4), (3/4, 3/4),$ and so on.

It's not self-intersecting in all points: the point $(0,0)$ for example is only hit once.

Added after comments: Here's how to see exactly which points are the points of self-intersection.

Subdivide $[0,1]^2$ into a grid of $2^n\times2^n$ squares. The $n$th iteration of the discrete Hilbert curve passes through each of these squares once. Number the squares from $1$ to $(2^n)^2$ in the order we pass through them, and let $H_n(k/(2^n)^2)$ be the center of the $k$th square, and extend $H_n$ to the whole interval $[0,1]$ by making it piecewise linear between the points $k/(2^n)^2$. The Hilbert curve $H:[0,1]\to[0,1]^2$ is defined by $H(x)=\lim_{n\to\infty}H_n(x)$.

Now suppose that $H(x)=H(y)$ where $x\neq y$, so that the point $H(x)\in[0,1]^2$ is a point where the curve self-intersects. Subdivide $[0,1]^2$ into a grid of $2^n\times 2^n$ squares, where $n$ is large enough so that the interval $(x-\epsilon,x+\epsilon)$ maps into one square, while $(y-\epsilon,y+\epsilon)$ maps into another square, for some small $\epsilon>0$. (This should always be possible by the construction of the Hilbert curve.) Since $H(x)$ and $H(y)$ belong to different squares, but they are equal, they must meet along the border of the squares, and this can only happen if one coordinate is a dyadic rational.

In the other direction, fix any point $(x,y)$ where one coordinate is a dyadic rational. This is a point on the border between two different squares in some $2^n\times 2^n$-subdivision of $[0,1]^2$. By the construction of the Hilbert curve, there exist a closed interval whose image is the first square, and another closed interval whose image is the second square. If $(x,y)$ is an interior point, by the way the Hilbert curve snakes around, we can always make sure those two intervals are disjoint. Since both intervals map surjectively onto the border between our two squares, there exists a point $x$ in the first interval and a point $y$ in the other interval such that $H(x)=H(y)$.

share|improve this answer
    
For the center (1/2, 1/2) it looks like it is being approached by 2 points ($(1/2-1/2^n,1/2-1/2^n)$ and $(1/2-1/2^n,1/2+1/2^n)$, and a line (all points between $(1/2+1/2^n,1/2-1/2^n)$ and $(1/2+1/2^n,1/2+1/2^n)$). So it looks like (from this intuitive argument) that every point (except some like $(0,0)$ around the edges of the square) are approached in a similar scenario and so might be covered by a non-finite set of points. Does that sound right? –  Mitch Mar 29 '11 at 17:28
    
Almost all points are only hit once. Those interior points with at least coordinate a dyadic rational are hit either 2,3 or 4 times. I've edited my answer with an argument for this. –  Samuel Mar 30 '11 at 2:09
    
It's still not clear to me which points overlap, and by how much when they do. That is, given point $(j,k)$, what is it's multiplicity? How about just for $(1/2, 1/2)$? –  Mitch Apr 4 '11 at 15:48
    
If there is an overlap on $(j,k)$, then $H(x)=H(y)=(j,k)$ for some $x\neq y$. By the construction of the curve, if $H_n(x)$ belongs to some square in a $2^n\times2^n$-grid, then $H(x)$ belongs to the same square. Since $x\neq y$, $H(x)$ and $H(y)$ must belong to different squares for some sufficiently large $n$. Since $H(x)=H(y)$, these squares must be adjacent. How many such squares are there? At most 4 (but usually just 2). As for $(1/2,1/2)$, $H(x)$ and $H(y)$ can belong to four different squares, but the two squares to the right will actually meet where $x=y$. The multiplicity is three. –  Samuel Apr 5 '11 at 15:37
    
@Mitch: (cont.) You can calculate $H(1/6)=H(1/2)=H(5/6)=(1/2,1/2)$ by counting how many squares the $n$th discrete Hilbert curve $H_n$ passes through until it reaches one of the four squares touching $(1/2,1/2)$. If $H(x)=(1/2,1/2)$ where $0\leq x\leq 1/4$, then $H_n(x)$ is in the lower left square touching $(1/2,1/2)$, so we must have $x\in[1/6-1/2^{2n},1/6]$ (I'll leave how to calculate that as an exercise). –  Samuel Apr 5 '11 at 15:46

You can see some specific places where the curve is not 1-1 as follows. The various stages of the construction are controlled by a grid, and as the curve gets filled in, it approaches the edges (and corners) of the grid from each side. So in the limit, points in the square which lie on the edge of the grid at some stage of the construction will be in the image of at least two points of the peano arc. The interior corners will lie in at least 4 points. So this at least shows it is not 1-1.

share|improve this answer

This is actually elaborated in the wiki article on Space-filling curves.

The short of it is that the Peano curve is continuous, $[0,1]$ is compact and $[0, 1]^2$ is Hausdorff, so if it were injective it would be a homeomorphism (we already know its surjective).

The missing bit is that it is everywhere self-intersecting but I feel this may be shown through arbitrarily restricting the domain - it is continuous, after all, so there is hope.

share|improve this answer
3  
I think Mitch already knew this part (he mentioned the non-existence of a homeomorphism). The question is about specifically seeing how, where and why the curve self-intersects, which may seem counterintuitive since all intermediate curves at finite stages of its construction don't. –  joriki Mar 29 '11 at 15:03
1  
It seems counterintuitive, yes; but there is a "qualitative" heuristc remark which can highlight this fact. In fact, as you can see from the pictures, if one sets $\delta_n :=$ minimum distance separating each couple of blocks the curve is made of at the $n$th step*, then $\delta_n=2^{-n}$; therefore in the limit (i.e. when the iteration gets closer and closer to *Peano's curve) $\delta_n\to 0$, i.e. the blocks become closer. Of course, this is a purely heuristic argument, but I think it can help visualizing how things go. –  Pacciu Mar 29 '11 at 15:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.