Entropy-Bounded Representation of Point Grids

Arash Farzan, Travis Gagie, and Gonzalo Navarro

We give the first fully compressed representation of a set of m points on a n x n grid, taking H+o(H) bits of space, where H = log_2 binomial(n^2,m) is the worst-case entropy of the set. This representation supports range counting, range reporting, and point selection queries, with a performance that is comparable to that of uncompressed structures and that improves upon the only previous compressed structure. Operating within entropy-bounded space opens a new line of research on an otherwise well-studied area, and is becoming extremely important for handling large datasets.