4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time

In the orthogonal range reporting problem we must pre-process a set P of multi-dimensional points, so that for any axis-parallel query rectangle q all points from q ∩ P can be reported efficiently. In this paper we study the query complexity of multi-dimensional orthogonal range reporting in the pointer machine model. We present a data structure that answers four-dimensional orthogonal range reporting queries in almost-optimal time O(log n log log n + k) and uses O(n log4 n) space, where n is the number of points in P and k is the number of points in q ∩ P. This is the first data structure with nearly-linear space usage that achieves almost-optimal query time in 4d. This result can be immediately generalized to d ≥ 4 dimensions: we show that there is a data structure supporting d-dimensional range reporting queries in time O(logd-3 n log log n + k) for any constant d ≥ 4. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.03161