Encoding 2D range maximum queries

Mordecai Golin, John Iacono, Danny Krizanc, Rajeev Raman, S. Srinivasa Rao

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 largest element in 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 upper and lower bounds by Brodal et al. (ESA 2010). We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
    Number of pages10
    StatePublished - 2011
    Event22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
    Duration: Dec 5 2011Dec 8 2011

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7074 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other22nd International Symposium on Algorithms and Computation, ISAAC 2011

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Encoding 2D range maximum queries'. Together they form a unique fingerprint.

    Cite this