Article ID Journal Published Year Pages File Type
431265 Journal of Discrete Algorithms 2015 18 Pages PDF
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 log⁡nlog⁡n bits.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,