Calculating the bounding box on the fly is not so good for three reasons.  Firstly you must compute the maximum box of all points within the Hilbert Curve bounds, so that the bounds are not so tight – it is better to compute them for the points you actually have, not the curve.  Secondly to reverse-engineer the Hilbert Curve into distances is very time consuming in itself.  Thirdly I found five points were rather better, so that the bounding “box” was in fact a pentagon.

I see, I probably misinterpreted the title and in the video.

One question: do you need to store this ‘maximum distances’ information into the pots? In my implementation I’m not using this trick (+ I’m not sure I’ve understood it properly) but I’m using a bounding box calculated on the fly while searching – is this the same idea?

I can calculate the bounding box of a branch-node easily derived from the current geo string

Apologies if you felt I was claiming that using Hilbert Curves for indexing on the Earth’s surface was original.  Of course it was not.  Martin Schoenert suggested I look at it, as it might be better than the Z-curve I originally proposed to use.  It was use of the observation that one can store, in each node of a binary search tree, the maximum distance to some fixed points and thereby effectively make “rectangles” even on the curved surface of a sphere that I though might be new.

https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/geohash/SpatialKeyAlgo.java

resulting in Z curves … here is a quadtree implemented with this

https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/trees/QuadTreeSimple.java

http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves