CO Range Reporting with Optimal Queries Requires Superlinear Space

This talk presents a space lower bound of Omega( N (log log N)^eps )
space, for some constant eps > 0, for any CO data structure capable of
solving three-sided range searching with the optimal query time of
O(log_B N + K/B).  These results extend to dominance reporting in 3D,
halfspace range reporting in 3D and K-nearest neighbor searching in 2D.
This bound provides the first non-constant space-separation between
query-optimal data structures in the IO and CO models.

The talk will also briefly mention new work on strengthening this lower
bound to Omega( N (log N)^eps ).

Joint work with Peyman Afshani (MADALGO, Aarhus University) and Norbert
Zeh (Dalhousie University).