Blog
About

11
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We present an optimal data structure for submatrix maximum queries in n x n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem. This gives a data structure of O(n) space that answers submatrix maximum queries in O(loglogn) time. It also gives a matching lower bound, showing that O(loglogn) query-time is optimal for any data structure of size O(n polylog(n)). Our result concludes a line of improvements that started in SODA'12 with O(log^2 n) query-time and continued in ICALP'14 with O(log n) query-time. Finally, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. In both previous results, partial Monge matrices incurred additional inverse-Ackerman factors.

          Related collections

          Most cited references 17

          • Record: found
          • Abstract: not found
          • Article: not found

          A Functional Approach to Data Structures and Its Use in Multidimensional Searching

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Geometric applications of a matrix-searching algorithm

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Trans-dichotomous algorithms for minimum spanning trees and shortest paths

                Bookmark

                Data structures & Algorithms

                Comments

                Comment on this article