Agreed. It's not even clear to me how this spiral qualifies as "space-filling". Where's the bijection between ℝ×ℝ and ℝ? Obviously if the curve were space-filling, the mapping is a function of the distance from the center, but this isn't bijective.
I'm exiting my area of expertise here, but Wikipedia claims that "no differentiable space-filling curve can exist." [1] A trivial modification of this curve – rounding the corners – would be differentiable without changing anything about it (it doesn't need the corners to cover all the space), so something doesn't smell right.
I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too? I think what's implied by the non-differentiabilty statement is that it must apply generally for infinitesimal cells. So you can round the turns but that needs space, and for general differentiability of the SFC you need to be able to do a rounded turn in (almost) no space at all.
The mapping does appear to be bijective - but I agree they should have presented the inverse in more detail! They state an SFC is a bijective function, but don't make the case for why O(i,j) is bijective? Again, I may be reading this wrong, I get a mild impostor syndrome attack every time I read a scientific article.
> I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too?
This is supposed to be close to my area of expertise, I will try to give a precise answer. The usual finite Hilbert curve is not space filling. the property of the Hilbert curve is that successive iterations converge to a continuous space filling curve.
There are well known techniques to transform continuous function in differentiable functions (https://en.wikipedia.org/wiki/Convolution#Differentiation) furthermore you can "smooth" the finite Hilbert curves so that the limit remains the same. But the true Hilbert curve (that is the limit of the finite approximations) will not be differentiable even if built as a limit of differentiable functions.
EDIT: On reconsideration, I may have been too hasty in dismissing your line of reasoning. If we consider a space-filling curve for the unit circle which is built like the onion curve (which is just a limit of round spirals), it WOULD be everywhere differentiable. I don't see much fundamental difference between that curve for circles and this curve for squares, at least as far as filling the space is concerned, so perhaps that does indicate there's something fishy with this curve. (This is a bit of a hand-wavy argument, though, and, on the other hand, there might indeed be a fundamental difference in the way the limits are reached for squares and circles, which is part of the argument I make at the end of my original comment. ).
(Note that this topic is also outside of my own area of expertise.)
Original comment:
Whilst I agree that a bijection between ℝ×ℝ and ℝ (or just from [0,1] to the unit square U) is to be demonstrated, I don't agree with the "rounding the corners" argument.
One could just as easily "round the corners" of the Hilbert curve without changing its space-filling nature. How much leeway you have for curving decreases at each subsequent iteration (as the squares you're filling get smaller) but this is true for both the Hilbert and Onion curves.
I believe the property of non-differentiality is only meant to apply to the limit of the curve as n approaches infinity, and, indeed, the limit of the Onion curve would be non-differentiable since it would have (infinitely many) corners. (Of course this doesn't prove that it IS a space-filling curve).
I wonder whether it is possible to find a bijection. Consider the unit interval to unit square f: I -> U. Consider the iterations 1,...,n,... of the curve. For each such iteration, we have a function f_i : I -> U. For each point p on the line, at each iteration we get a point on the square f(p) in U. The points (p_1, ... p_n, ...) that p maps to, form a sequence.
It remains to check:
1. Does each such sequence converge? (i.e., is the limite of the f_i, a function f: I -> U which is well-defined?)
2. If they do converge, is the convergence unique? (I.e., no two sequences converge to the same point - the function f is injective).
3. And, for each point p on the square, is there some sequence (p_1, ... p_n, ...) that converges to it? (Is the function f surjective?).
If we have these three, we have a bijection, but to prove (or disprove) this, we'd need to look at the mathematical definition of the onion curve (defined on p4 of the paper), but I'm not going to do this maths right now, especially not in a Hacker News comment, so it's left as an exercise to the reader ;)
Point is, I don't know at a glance whether this IS a space-filling curve, or not, and would be happy to hear the judgement either way. I'm not sure intuitive arguments are going to do it justice, and there may very well be some argument involving irrational points not being covered or a sequence that doesn't converge (a point which "travels infinitely far" as you iterate).
Peano published the original space-filling curve paper without diagrams, for fear that pictoral arguments may lead intuition astray. Indeed, I believe this to be the case for this curve, too, and perhaps only a mathematical proof in terms of the defined functions may settle this one way or the other.
> 2. If they do converge, is the convergence unique? (I.e., no two sequences converge to the same point - the function f is injective).
The curve given in the paper doesn't satisfy that requirement. O_j(x1, x2) is defined as a mapping from the (j × j) square to integers smaller than j² by a case distinction that includes O_j(x1, 0) = x1. If you want to use that curve to fill the unit square, you need to rescale it as o_j(y1, y2) = O_j(j•y1, j•y2)/j² so that all values involved stay in [0, 1]. Then for all y1, we have o_j(y1, 0) = j•y1/j² = y1/j, which decays to 0 as j grows to infinity. Hence the limit function is not bijective.
I'm exiting my area of expertise here, but Wikipedia claims that "no differentiable space-filling curve can exist." [1] A trivial modification of this curve – rounding the corners – would be differentiable without changing anything about it (it doesn't need the corners to cover all the space), so something doesn't smell right.
[1] https://en.wikipedia.org/wiki/Space-filling_curve#Properties