Linear space adaptive data structures for planar range reporting

Let S be a set of n   points on an n×nn×n integer grid. The maximal layer of S is a set of points in S that are not dominated by any other point in S. Considering Q   as an axes-parallel query rectangle, we design an adaptive space efficient data structure using layers of maxima (iterative maximal layers) for reporting the points in Q∩SQ∩S. Our data structure needs linear space and can be queried in time O(logε⁡n+Alogε⁡n+k)O(logε⁡n+Alogε⁡n+k). Here A is the number of layers of maxima with points in the query rectangle, k is the size of the output and ε   is a small arbitrary constant in the range of (0,1)(0,1). Also, A≤kA≤k. In the worst case, the query time of our data structure is O(klogε⁡n+k)O(klogε⁡n+k). Our model of computation is the word RAM with size of each word being Θ(log⁡n)Θ(log⁡n).