Please use this identifier to cite or link to this item:

Encoding 2D range maximum queries

Authors Golin, Mordecai Jay View this author's profile
Iacono, John
Krizanc, Danny
Raman, Rajeev
Satti, Srinivasa Rao
Shende, Sunil M.
Issue Date 2016
Source Theoretical Computer Science , v. 609, January 2016, p. 316-327
Summary We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array containing elements from an ordered set, encode the array so that the position of the maximum element in any specified range of rows and range of columns can be found efficiently. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode an array so that 2D-RMQ queries can be answered without accessing the array. We give tight upper and lower bounds on the expected effective entropy for the case when A contains independent identically-distributed random values, and give new upper and lower bounds for the case when the array contains few rows. The latter results improve upon the upper and lower bounds by Brodal et al. [4]. We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy. © 2015 Elsevier B.V.
ISSN 0304-3975
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science