2022/11/06 by Nekrich, Yakov, Rahul, Saladi
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2211.03161
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 nloglog n + k) and uses O(nlog4 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 nloglog n+k) for any constant d≥ 4.