Abstract

We give the first fully compressed representation of a set of m points on an n x n grid, taking H + o(H) bits of space, where H = lg ((n2)(m)) is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with complexities that go from O(1) to O(lg(2) n/lg lg n) per answer as the entropy of the grid decreases. Operating within entropy-bounded space, as well as relating time complexity with entropy, opens a new line of research on an otherwise well-studied area. (C) 2013 Elsevier B.V. All rights reserved.