On Space Efficient Two Dimensional Range Minimum Data Structures
The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=ma <...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 a data structure of size O(N/c) bits requires Omega(c) query time, for any c where 1a parts per thousand currency signca parts per thousand currency signN. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog (2) c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(Na <...min {m,log n}) bits with O(1) query time, assuming ma parts per thousand currency signn. This leaves a gap to the space lower bound of Omega(Nlog m) bits for this version of the problem.
range minimum query cartesian tree time-space trade-off indexing model encoding model