4 ms·

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 spac

• tromp 3y ago
  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?! __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| ;__ __| | |__ __,__ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__|
• sp332 3y ago
  So you converted your 2D space into another 2D space?
• dwallin 3y ago
  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.
  • jandrewrogers 3y ago
    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.