Please use this identifier to cite or link to this item:
Title: Encoding 2-D Range Maximum Queries
Authors: Golin, M. J.
Iacono, J.
Krizanc, D.
Raman, Rajeev
Rao, S. S.
Shende, S.
First Published: 21-Oct-2015
Publisher: Elsevier
Citation: Theoretical Computer Science, 2016, 609(2) pp. 316–327
Abstract: We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array $A$ of ordered values, to pre-process it so that we can find the position of the smallest element in the sub-matrix defined by a (user-specified) range of rows and range of columns. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode $A$ so that 2D-RMQ queries can be answered without access to $A$. We give tight upper and lower bounds on the expected effective entropy for the case when $A$ contains independent identically-distributed random values, and new upper and lower bounds for arbitrary $A$, for the case when $A$ contains few rows. The latter results improve upon previous upper and lower bounds by Brodal et al. (ESA 2010). In some cases we also give data structures whose space usage is close to the effective entropy and answer 2D-RMQ queries rapidly.
DOI Link: 10.1016/j.tcs.2015.10.012
ISSN: 0304-3975
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2015 Elsevier. This manuscript version is made available after the end of the embargo period under the CC-BY-NC-ND 4.0 license
Description: The file associated with this record is under a 24-month embargo from publication in accordance with the publisher's self-archiving policy, available at The full text may be available in the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
TCS-sub-all.pdfPost-review (final submitted)334.12 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.