Hacker News Reader

Comment by tromp | Hacker News Reader

> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89

But points with a large difference in their single curve coordinate can be either far apart or close together. E.g. on this 16 point Hilbert curve

     __.  .__ 
     __|  |__ 
    |   __   |
    |__|  |__|

the '.' marked points at 1/16th and 15/16th along the curve are adjacent.

View on HN

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

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?!

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

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

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.

Reply on news.ycombinator.com