this query time is optimal. The best previously known four-dimensional data structure supports queries in $O(\log n + k)$ time. According to the lower bound of [Pǎtraşcu]{}, any data structure that consumes $O(n\mathtt{polylog}(n))$ space requires $\Omega(\log n/\log \log n)$ time to answer four-dimensional queries; this lower bound is also valid for emptiness queries. In this paper we describe, for the first time, a data structure that achieves the optimal $O(\log n/\log\log n+k)$ query time for the four-dimensional range reporting problem. Henceforth $k$ denotes the number of points in the query range.

Previous solutions of this problem employed range trees to solve the orthogonal range reporting problem in four dimensions. To answer a query, we must navigate a node-to-leaf path[^3] in a range tree and answer a three-dimensional range reporting query in every node on that path. By the lower bound for three-dimensional reporting, we have to spend $\Omega(\log\log n)$ time in every visited node. The node degree of the range tree is bounded by $\log^{O(1)} n$; a higher node degree would lead to prohibitively high space usage because we must store a separate data structure for every range of node children. Thus we must navigate along a path of $\Omega(\log 