Aries512's blog

By Aries512, 10 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.