Imagine we have a n x m rectangular grid of some reasonable size (say, only 1000x1000), and for some of the positions on grid we have elements, each with an associated range a..b.
The query is: for the position x,y on the grid with the value z, find the closest neighbour on the grid such that a<=z<=b.
Without the range constraint, the task is fairly easy with the use of kd-trees or other structures. How can we efficiently solve the problem with the additional range constraint? I'm interested in approximation or probabilistic algorithms too if there are any.
It is possible to use an interval tree for values and store a kd-tree (or something else) in each node just for the points with values in range. This way, you will need O(log n) kd-tree queries per query and log n time more memory used.