Hacker News Reader

Comment by wolframhempel | Hacker News Reader

It's an important point. We've ended up using two Hilbert curves, rotated by 90 degrees to tackle this problem. If it is close on either, it is close in 2D space

View on HN

Interesting. So one might think that being close together in 2D space corresponds to being close on

BOTH cartesian coordinates / EITHER Hilbert coordinate

And that being far apart in 2D space corresponds to being far apart on

EITHER cartesian coordinate / BOTH Hilbert coordinates

But if we consider the two commas below which are close together in 2D space, we see they are far apart in any rotation of this Hilbert curve?!

        __ __    __ __
    |__|   __|  |__   |__|
     __   |__    __|   __
    |  |__ __|  ;__ __|  |
    |__    __,__ __    __|
     __|  |__    __|  |__
    |   __   |  |   __   |
    |__|  |__|  |__|  |__|

As mentioned in other replies, this doesn't fully solve a lot of the cases. I think z order curves might actually be better here, they are slightly less accurate individually, but in a way that would seemingly minimize the worst case results when taking the minimum of the two. But at that point you are probably better off using a single z-order curve and using the coordinates to check the manhattan or Chebyshev distance using bitwise operations.

I would second the use of Z-order curves. Hilbert curves were famously known as more optimal on spinning disk in a specific context a few decades ago. Inertia has kept them top-of-mind even though modern systems do not have the problems Hilbert curves were better at solving and those curves are more complex to use than e.g. Z-order curves.

So you converted your 2D space into another 2D space?

Reply on news.ycombinator.com