###
FIX to Entropy-Bounded Representation of Point Grids

#### Level: Medium

There is a mistake in Thm. 2 that fortunately does not propagate to the main
result, Thm. 1. The error is in the accounting for the space of the
wavelet-tree based structure of [2]. The final space can be written as
*t log s + o(t) log s + O(t+n)*, where *s=sigma*.
Thm. 2 is used in four parts later. The first one is at the end
of Sec. 4.1, where the space is *H + o(H) + O(m logloglog m)* instead
of *H + o(H) + O(m)*. Now the last term is not *o(H)* for
*m = Omega(n^2/(loglog n)^O(1))*.

The second and third parts are in Sec. 4.2 and 4.3 respectively, where it does
not affect the results. The last part is Sec. 4.4. This causes no problems
either. Say we use it for *m < n log n*, then one can see that the space
is *H + o(H)* in that range.

Overall, Thm. 4 is affected, as the space is actually *H + o(H) +
O(m logloglog m + log n)*. This impacts in case (b) of Thm. 1, as it now
holds only if *m = o(n^2/polyloglog n)*. Yet, we use this case only to
cover the area *m = O(n^2/log^(1/4) n)*, which stays covered.

Another small fix is that Table 1 gives time *(k+1) lg^2 n* for
reporting in row Thm. 1, whereas the correct figure is *(k+1) lg^2
(n^2/m)* as said everywhere else.

The journal version will of course have this fixed.