Spatial hashing
Background
Spatial hashing is a very simple technique, good for data which is moving
in space. One problem with it is that
it does not do a very good job on distributions where the input
points lie on lower-dimensional manifolds (like points on a 2D surface in
3D), but the queries might be very far from the input points.
Can we extend spatial hashing to handle this case?
Multi-resolution approach
One idea would be to make a multi-resolution spatial hash structure,
in which the lower-resolution voxels do not contain the data points,
but perhaps pointers to occupied higher-resolution voxels, or perhaps
a sample of the data from the occupied higher-resolution voxels.
Can you find a way to make a spatial hash structure which is still
O(n) size, but which has decent query time and accuracy on all
nearest-neighbor queries?