Entropy-bounded representation of point grids
Author
Abstract
We give the first fully compressed representation of a set of m points on an n×n grid, taking H+o(H) bits of space, where View the MathML source 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(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.
General note
Artículo de publicación ISI
Identifier
URI: https://repositorio.uchile.cl/handle/2250/126797
DOI: DOI: 10.1016/j.comgeo.2013.08.002
Quote Item
Computational Geometry Volume 47, Issue 1, January 2014, Pages 1–14
Collections