It's pretty easy to imagine a counter-example that would have you traverse the length of the map, when the best route would be to detour on an existing traversal. Consider:

    1...2...3...4...5
    7...............6
    8.......9........
    13..12.....11..10

versus

    1...2...3...4...5
    13..............6
    12......9........
    11..10......8...7

Good point, though I'm not convinced Hilbert really avoids this. For example, look at n=3 here:

http://www.texample.net/media/tikz/examples/PNG/hilbert-curv...

This might lead to say

. . . . . . . .

1 . . . . . . 2

4 . . . . . . 3

. . . . . . . .

when

. . . . . . . .

1 . . . . . . 4

2 . . . . . . 3

. . . . . . . .

is more efficient.

Generally speaking, it seems this is basically TSP.

I tried describing here https://www.reddit.com/r/programming/comments/6oxra8/using_h... why I think that this is theoretically a TSP problem, I don't consider that necessarily the best way to treat it. tl;dr is, that at least to me, at the time, for this problem, the speedup of an optimal solution wouldn't have outweighed the additional thinking time to get to that optimal solution (and, most importantly, to actually make it useful; after all, I wasn't actually drawing a path, I was outputting a list of names).

You can even see that in the argument I added to the post; while a zig-zag line might've been, in theory, a stupider, easier way to solve the problem, in practice it would've meant spending some time thinking about the right discretization. With a Hilbert-curve, I could just choose some n that is definitely large enough and be done with it and the additional cost of the more complicated curve doesn't really factor in, as I could just copy-paste it anyway.

But yes. The theoretical problem is a TSP and with the right set of tools, I could've added some efficiency to the search by viewing it as such.

I think is TSP only if you start by the first point in the ordered list. If you start any other point, you will be going in only one direction (top-bottom/left-right or bottom-top/left-right) (See how the space is filled)

Given the precision of the points, lexicographical order on (x,y) would essentially be lexicographical order on just x, which then induces a lot of jumping around the map.

Yeah, sorry I meant like lexicographic on x, then swapping between lexi and reverse-lexi on y. Basically snaking back and forth.

Basically, what others have replied is true. But, in essence, yes, I now believe that this would've worked too, if you choose an appropriate discretization of the grid. Hilbert Curves probably were simply the Hammer I had lying around. In the end, it didn't really matter, given that the actual Hilbert Curve part was mostly copy-pasted, but at least it gave me the opportunity to actually use them (and learn from it).

It's a long walk from (1, 10) to (2, 1).

Yeah sorry I meant like snaking back and forth, which you're right is not the same as pure lexicographic.

Yeah, the length of such a snake is equal to the Hilbert curve.

Yes, but we wouldn't actually walking the whole snake, just as we are not walking the whole Hilbert curve. We are walking the point cloud in the order dictated by either, and those will, in general, differ.

I have added a section about this question to the post. Let me know what you think :)

d