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.

Is there a space-filling curve $C$ that has the property that, if $C$ passes through $p_1=(x_1,y_1)$ at a distance $d_1$ along the curve, and through $p_2$ at $d_2$, then if $|p_1 - p_2| \le a$, then $|d_1 - d_2| \le b$, for some constants $a$ and $b$? In other words, any two points of the plane within distance $a$ are separated by at most $b$ along $C$. Call this property distance locality. So I am asking whether a curve exists mapping $\mathbb{R}$ to $\mathbb{R}^2$ with distance locality.

Although I doubt the answer differs, permit me also to ask the same question for $\mathbb{Q}^2$, and for $\mathbb{Z}^2$.

I have little experience with the properties of the known space-filling curves. Those better schooled on this topic can likely answer these questions easily. Thanks!

Addendum. I noticed a paper just released today which is focused on "locality properties" of 3D space-filling curves: "An inventory of three-dimensional Hilbert space-filling curves," arXiv:1109.2323v1 [cs.CG]. The author explores several different locality measures that have been considered in the literature, and cites a wealth of references.

share|improve this question
    
A curve doesn't map ${\bf R}^2$ to $\bf R$, it maps an interval in $\bf R$ to ${\bf R}^2$. –  Gerry Myerson Sep 10 '11 at 12:20
    
@Gerry: You are right! What I meant is the reverse. I will repair. –  Joseph O'Rourke Sep 10 '11 at 12:32
add comment

2 Answers 2

up vote 3 down vote accepted

The first problem is that "distance along the curve" is not meaningful for a space-filling curve -- the usual definition of distance for smooth curves (limit of approximating polygons) leads to the distance between two general points on the curve being infinite.

If you replace "distance along the curve" with "difference in parameters", then I can do it for $[0,\infty)\to\mathbb R^2$, but getting a doubly-infinite domain seems to be impossible.

Possible for $[0,\infty)\to \mathbb R^2$: Divide the plane into unit squares and number them in a spiral going out from the origin:

12 11 10  9  .
13  2  1  8  .
14  3  0  7  .
15  4  5  6 21
16 17 18 19 20

The classic Peano curve construction yields a space-filling curve $[0,1]\to[0,1]^2$. Put countably many of these together into $f:\mathbb [0,\infty)\to\mathbb R^2$, such that $f([n,n+1/2])$ fills the square numbered $n$ in the diagram, and $f([n+1/2,n+1])$ is just a simple connection from the endpoint of one Peano curve and the begining of the next.

This $f$ fills space but does not satisfy distance locality. But $g(t) = f(t^3)$ does. The cubic growth ensures that each winding in the spiral occupies a bounded amount of $t$, so the parameter distance between each square and any of its 8 neighbors is globally bounded.

Impossible for $\mathbb R\to \mathbb R^2$: Assume $f:\mathbb R\to\mathbb R^2$ is space-filling and satisfies your distance locality criterion. With appropriate scaling and translation we can assume $f(0)=(0,0)$ and $a=b=1$. We can then prove by induction on $n$ that $|f(t)|<n \Rightarrow |t|<n$ for all integers $n$, and therefore $|f(t)|>|t|-1$ in general. Then let $D=1+\max\limits_{|t|\le 1}|f(t)|$, and consider the two sets $$ P = \{ f(t) \mid t > 1 \land |f(t)| > D \} $$ $$ M = \{ f(t) \mid t < -1 \land |f(t)| > D \} $$ $P$ and $M$ are both nonempty -- one contains $f(D+1)$, the other $f(-(D+1))$ -- and their union is the connected set $\{x\in \mathbb R^2\mid |x|\ge D\}$. Therefore their closures must intersect. But near a point where the closures meet, there must be $t$s that violate distance locality.

share|improve this answer
    
Yes, excellent point, I should have used "difference in parameters" just as you suggest. –  Joseph O'Rourke Sep 10 '11 at 12:53
    
These are subtle arguments! I am surprised by both results, both by the positive for $[0,\infty)$ and the negative for $(-\infty,\infty)$. It's not completely clear to me that the Peano curves can be connected as desired, but I do see the overall idea, which is clever. Thanks for your attention! –  Joseph O'Rourke Sep 11 '11 at 15:36
    
The connecting pieces can just be uniform rectilinear motions directly from one point to another. They will cross ground also hit by the Peano curves themselves, but that doesn't matter: a space-filling curve is allowed to hit the same point more than once. (Alternatively, if you use a combination of Peano and Hilbert curves -- of which one has the endpoints at opposing corners for the unit square, the other at neighboring corners -- in appropriate rotations, you can avoid the need for connectors completely). –  Henning Makholm Sep 11 '11 at 20:14
add comment

Let $f:{\bf Z}\to{\bf Z}^2$ be one-one and onto. Suppose that for all pairs of adjacent lattices points $p$ and $q$ there exist integers $b$, $m$, and $n$ such that $f(m)=p$, $f(n)=q$, and $|m-n|\le b$. Suppose without loss of generality that $f(0)=(0,0)$. For any positive integer $d$, if $p$ is a lattice point $d$ steps away from the origin, then we must have $f(n)=p$ for some $n$ with $|n|\le bd$. But the number of lattice points $d$ steps away from the origin grows as the square of $d$, while the numbers of integers $n$ with $|n|\le bd$ grows linearly with $d$, contradiction. So there isn't a map satisfying "distance locality", even for distance $a=1$.

share|improve this answer
    
That is a very clean argument, Gerry: linear vs. quadratic. Nice! –  Joseph O'Rourke Sep 11 '11 at 15:31
add comment

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.