So about four years ago I came across this paper by Martin Wattenberg, where he described the Jigsaw Map:
I liked the idea of it, but could not find any implementation of the H-curve required to build one, so into the mental archives of half-forgotten interesting ideas his paper went.
A few months ago I realized that there is actually a really, really simple way to construct these curves - simpler than… I would say almost anything that isn’t a Z-curve. I lacked the motivation to implement it though. Then yesterday @mootari shared a cool work-in-progress on twitter that relied on a different Hamiltonian space-filling curve, reminding me I still had that half-finished idea of creating H-curves. So I just spent the better part of my Sunday writing this notebook.
The most interesting property of the H-curve is the strong locality property, which is better than for any other known curve (and conjectured to be optimal). It becomes almost intuitively visible if we plot the curve as a gradient:
Maybe other people here will find a use for that. For example, as an alternative to the Hilbert curve in
- @mourner’s Hilbert Curve Packing notebook
- @Fil’s notebook on motion rugs (I actually suggested the H-curve to the inventor of the motion rug, but if he even checked out the papers I linked there, I guess he just ran for the hills as well after reading them - can’t blame him)
Other potential next steps: implementing my own ZH-hybrid?
(It probably won’t have the optimal locality that a pure H-curve has, but it has the alternative feature that the two points that are the furthest away from each other are also in opposite corners in 2D)