The two dimensional range minimum query problem is to preprocess a static two-dimensional matrix A with N elements so that reporting the minimum element in a rectangular range can be done efficiently. 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. This lower bound holds for any dimension. In two dimensions, we complement the 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. Taking c to be O(1), this is the first O(1) query time algorithm using optimal O(N) bits additional space.
(Based on a paper by Brodal, Davoodi, and Rao at ESA 2010.)