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.
Best Answer
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:
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.