Aarhus University Seal

On Space Efficient Two Dimensional Range Minimum Data Structures

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
The two dimensional range minimum query problem is to preprocess a static two dimensional m by n 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 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 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 additional space which can be preprocessed in O(N) time and achieves O(clog2 c) query time. For c = O(1), this is the first O(1) query time algorithm using optimal O(N) bits additional space. For the case where queries can not probe A, we give a data structure of size O(N· min {m,logn}) bits with O(1) query time, assuming m ≤ n. This leaves a gap to the lower bound of Ω(Nlogm) bits for this version of the problem.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume6347, Part 2
Pages (from-to)171-182
Number of pages12
Publication statusPublished - 2010
EventAnnual European Symposium on Algorithms. ESA 2010 - Liverpool, United Kingdom
Duration: 6 Sept 20108 Sept 2010
Conference number: 18


ConferenceAnnual European Symposium on Algorithms. ESA 2010
CountryUnited Kingdom

Bibliographical note

Title of the vol.: Algorithms – ESA 2010. 18th Symposium : proceedings
ISBN: 3642157807, 9783642157806

See relations at Aarhus University Citationformats

ID: 19174612