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.