کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428489 | 686780 | 2016 | 6 صفحه PDF | دانلود رایگان |
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 Θ(logn)Θ(logn).
Journal: Information Processing Letters - Volume 116, Issue 5, May 2016, Pages 361–366