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.