The 2-d range minimum problem

Pooya Davoodi

The two dimensional range minimum query problem is to preprocess a static two dimensional array A of size m×n=N such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using O(N/c) bits additional space requires Ω(c) query time, for any c where 1 ≤ c ≤ N. In particular, this lower bound holds for the one dimensional version of the problem. We complement this lower bound with an indexing data structure of size O(N/c)$ bits additional space which can be preprocessed in O(N) time and achieves O(c log2 c) query time. For c=O(1), this is the first optimal algorithm using O(N) bits additional space achieving O(1) query time. For the case where queries can not probe A, we give a data structure of size O(N·min{m,log n}) bits with O(1) query time, assuming mn. This leaves a gap to the lower bound of Ω(N log m) bits for this version of the problem.