Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431265 | Journal of Discrete Algorithms | 2015 | 18 Pages |
Abstract
In this work we show that given a set S of n points with coordinates on an n×nn×n grid, we can construct data structures for (i) reporting and (ii) counting the maximal points in an axes-parallel query rectangle in sub-logarithmic time. We assume our model of computation to be the word RAM with size of each word being lognlogn bits.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ananda Swarup Das, Prosenjit Gupta, Kishore Kothapalli, Kannan Srinathan,