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.