On Space Efficient Two Dimensional Range Minimum Data Structures

On Space Efficient Two Dimensional Range Minimum Data Structures

0.00 Avg rating0 Votes
Article ID: iaor20123972
Volume: 63
Issue: 4
Start Page Number: 815
End Page Number: 830
Publication Date: Aug 2012
Journal: Algorithmica
Authors: , ,
Keywords: heuristics: local search, computers: data-structure
Abstract:

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m·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 Ω(c) query time, for any c where 1≤cN. 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(clog2 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(N·min{m,log n}) bits with O(1) query time, assuming mn. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.

Reviews

Required fields are marked *. Your email address will not be published.