IMPROVED BOUNDS FOR CACHE-OBLIVIOUS RANGE REPORTING

by Norbert Zeh

This talk presents the first cache-oblivious 3-d dominance reporting data
structure that achieves the optimal query bound while using o(N log N)
space.  A consequence of this result is the existence of an o(N log N)
space data structure for optimal cache-oblivious 3-sided range reporting
in the plane---also a new result---as well as new space bounds for
optimal cache-oblivious 2-d and 3-d orthogonal range reporting.

The talk will also announce a stronger lower bound for optimal
cache-oblivious 3-d dominance reporting, 2-d three-sided range
reporting, and 3-d halfspace range reporting but will not discuss it due
to lack of time.

Joint work with Peyman Afshani (MADALGO, Aarhus Universitet)