Some combinatorial applications of spacefilling curves
www2.isye.gatech.edu
www2.isye.gatech.edu
Another benefit I see is that you could quickly generate many heuristic solutions by randomly translating, rotating and/or uniformly scaling the curve, and then choose the best.
It does look like it can produce crossing edges, which are suboptimal in Euclidean space, but these are easy to rectify -- whenever 2 edges cross, just swap their endpoints for a quick guaranteed improvement. Because doing this strictly decreases the total tour length, and every such decrease is lower-bounded by the smallest such decrease among all (nCities choose 4) possible sets of 4 cities, repeatedly doing this must eventually terminate in a crossing-free tour.
The space-filling curve approach strikes me as a decent way to get a starting point, not something to use unmodified. But I've no idea whether that's true -- does the structure of such a solution lend itself well to simple iterative improvements or not?
Because once you have that, you just need to sort simple integers, which you can do in linear time with a radix sort. (Again ignoring bit lengths.)
What am I missing?
This describes an implementation using a Rolodex to plan Meals on Wheels routes.
Also, a trivial application is image compression. Let's say you have a PNG image. PNG uses zlib, so if instead you take a raw bitmap and compress it with ZSTD, it typically will be better, but if you also sort pixels by the Hilbert curve first and then compress with ZSTD, it will be typically even better.
I'm guessing this application would be selecting an ordering to engage multiple simultaneous targets in minimal-ish time - MIRV warheads or missiles launched in a barrage.
But Hilbert curves are complicated. If you have n dimensions, you can simply take the sequence of bits describing the position in each dimension and interleave them, forming a longer sequence of bits. It's not nearly as nice of a curve -- adjacent points along the line are not necessarily close in n-dimensional space the way they would be with a Hilbert curve -- but it's simple to calculate and proves that you can generalize this stuff to any number of dimensions.
This interleaving produces what is called a Z-curve or Morton curve. It's not continuous like the Hilbert curve, so mathematically you might not call it a space-filling curve but in CS-land, you probably would.