Counting Maximal Points in a Query Orthogonal Rectangle*

摘要

In this work, we propose a solution with sub-logarithmic query time for counting the number of maximal points in an axis parallel query rectangle. The problem has been previously studied in [3] and [5]. To the best of our knowledge, this is the first sub-logarithmic query time solution for the problem. Our model of computation is the word RAM with word size of Θ(log n) bits.