Linear space adaptive data structures for planar range reporting

摘要

Let S be a set of n points on an n x 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 boolean AND S. Our data structure needs linear space and can be queried in time 0 (log(epsilon) n + A log(epsilon) 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 epsilon is a small arbitrary constant in the range of (0, 1). Also, A <= k. In the worst case, the query time of our data structure is 0 (k loge n + k). Our model of computation is the word RAM with size of each word being O(log(epsilon) n + k). (C) 2016 Elsevier B.V. All rights reserved.