each recursive sub-structure of the grid. This data structure is based on the notion of a $t$-shallow cutting. We show that a shallow cutting can be “covered”, in a certain sense, by a set of rectangles. Every covering rectangle contains a small number of points and is unbounded along the third dimension. We can specify the relevant points by their positions in rectangles. This approach essentially reduces the problem of storing points in a recursive grid to the problem of storing points in a compact range tree aka the ball inheritance problem [@Chazelle88; @ChanLP11].

  Ref.                                       Space                       Range-Minima                                 Five-sided
  ----------------------------- ------------------------------- ------------------------------- -------------------------------------------------------
  [@Chazelle88]                             $O(n)$               $O(\log^{1+{\varepsilon}} n)$   $O(\log^{1+{\varepsilon}} n+ k\log^{{\varepsilon}}n)$
  [@FarzanMR12]                             $O(n)$                  $O(\log n \log\log n)$                                 -
  [@ChanLP11]                    $O(n\log^{{\varepsilon}} n )$         $O(\log\log n )$                           $O(\log\log n + k)$
  [@KarpinskiN09] + [@Chan13]        $O(n (\log\log n)^3)$             $O(\log\log n)^2$                   $O((\log\log n)^2 + k\log\log n)$
  Our                                       $O(n)$                $O(\log^{{\varepsilon}} n)$               $O((k+1)\log^{{\varepsilon}}n)$
  Our                                  $O(n\log\log n)$                 $O(\log\log n)$                          $O((k+1)\log\log n)$

  : Previous best and new results on range minima and five-sided range reporting problems.[]{data-label="tab:rangemin"}

#### Multi-Dimensional Range Reporting.

Orthogonal range reporting queries can be answered in $O(\log \log n + k)$ time in two [@Overmars88; @AlstrupBR00] and three dimensions [@Chan13]. By the lower bound for predecessor queries [@PatrascuT06], 