Onion Curve: A Space Filling Curve with Near-Optimal Clustering (2018)

A spiral can't fill RxR as you say, but in this case they're only trying to fill ZxZ, which is easy.

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.

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.

This is does seem like a trivial optimization over striping.

If your target area is small relative to your potential search space -- imagine your grid is a million by million rows and you are selecting rectangles that are between 10 and 1000 units wide in either dimension -- you'll end up with height or width number of rows or columns to search, most of the time.

Meanwhile, if your target area is large compared to your potential search space ... you also end up with height or width number of L-shaped segments to search along. You only end up with fewer segments if your search area happens to include the center.

Also, not actually a space-filling curve.