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 an n x n grid, taking H+o(H) bits of space, where
H = lg binomial(n^2,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.