Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414301 | Computational Geometry | 2014 | 14 Pages |
Abstract
We give the first fully compressed representation of a set of m points on an n×nn×n grid, taking H+o(H)H+o(H) bits of space, where H=lg(n2m) is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with complexities that go from O(1)O(1) to O(lg2n/lglgn)O(lg2n/lglgn) 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arash Farzan, Travis Gagie, Gonzalo Navarro,