cutting, but construct a data structure supporting 2-d dominance minimum queries for every cell. We replace the top data structure with a data structure from [@ChanLP11]. This data structure contains $O(n/\log n)$ points and uses $O(n)$ space (on the top recursion level). We can decompose a four-sided query to $O(\log\log n)$ dominance queries and $O(\log\log n)$ minima queries on top data structures as described in Section \[sec:recur\]. Thus the answer to a (four-sided) range minima query in 2-d is the minimum of the answers to $O(\log\log n)$ local queries. The total query time $O(\log^{{\varepsilon}}n\log\log n)$. We can get rid of the $\log\log n$ term by replacing ${\varepsilon}$ with an arbitrary ${\varepsilon}'< {\varepsilon}$.

Four-Dimensional Dominance Range Reporting {#sec:fourdim}
==========================================

In this section we describe a data structure that answers dominance range reporting queries in $O(\log n/\log \log n+k)$ time. We start by explaining why previous methods require $\Omega(\log n)$ time. Then we describe the main idea of our approach and show how it can be used to reduce the query time by a factor $O(\sqrt{\log\log n})$. Then we will present a complete solution.

#### Range Trees.

Four-dimensional queries are reduced to three-dimensional queries using a range tree. A range tree $T$ 