is closely related to the special case of three-dimensional range reporting when the query range is bounded on five sides. All previous results, except for [@FarzanMR12], can be extended to support five-sided queries.

Range minima queries are to be contrasted with two-dimensional emptiness queries. In this problem we store a set of two-dimensional points; given an axis-parallel query rectangle $Q$, we must decide whether $Q\cap P=\emptyset$. Emptiness queries can be answered in $O(\log^{{\varepsilon}}n)$ time using an $O(n)$-space data structure [@ChanLP11], or in $O(\log \log n)$ time using an $O(n\log \log n)$-space data structure [@AlstrupBR00; @ChanLP11].

In this paper we demonstrate that the gap between range emptiness and range maxima in two dimensions can be closed completely. We present a data structure that uses $O(n)$ space and answers range minima queries in $O(\log^{{\varepsilon}} n)$ time. We also describe a data structure that uses $O(n\log\log n)$ space and answers queries in $O(\log\log n)$ time. Our results can be extended to five-sided queries in three dimensions.

Our data structure employs the standard recursive grid approach frequently used in orthogonal range searching problems [@AlstrupBR00; @ChanLP11; @FarzanMR12; @KarpinskiN09; @ChanNRT18]. The novel part of our method is a compact data structure supporting three-dimensional dominance queries for 