{#sec:intro}
============

Orthogonal range searching is a fundamental and extensively studied data structuring problem [@McCreight85; @Chazelle86; @ChazelleG86; @ChazelleG86a; @ChazelleE87; @Chazelle88; @Overmars88; @Chazelle90a; @Chazelle90b; @SubramanianR95; @VengroffV96; @AlstrupBR00; @AlstrupBR01; @Nekrich07isaac; @Nekrich07; @Nekrich07algorithmica; @KarpinskiN09; @NN12; @ChanLP11; @Chan13]. In this problem we store a set of multi-dimensional points $P$ in a data structure so that for an arbitrary axis-parallel rectangle $Q$ some information about points in $Q\cap P$ must be returned. Different variants of range searching queries have been studied by researchers: an orthogonal range reporting query asks for the list of all points in $P\cap Q$; an orthogonal range emptiness query determines whether $P\cap Q=\emptyset$, an orthogonal range counting query asks for the number of points in $P\cap Q$. In the range minima/maxima problem each point is assigned a priority and we must return the point of smallest/highest priority in $P\cap Q$.

In this paper we study the orthogonal range reporting and range minima problems. We improve the query time of linear-space range minima data structure in two dimensions from $O(\log n\log \log n)$ to $O(\log^{{\varepsilon}} n)$. Henceforth $n$ denotes the total number of points in the data structure and ${\varepsilon}$ is an arbitrarily small positive constant. We also describe a data structure 