Proving the Exterior (Outer) Measure of Rectangle is Equal to Volume

I'll try to answer why the number of cubes in $\mathcal Q'$ is $O(k^{d-1})$ as $k\to\infty$. The set $\mathcal Q'$, by the way, is the set of cubes that intersect the original rectangle and its complement. In $3$-D, this would be the cubes that cover the faces of the rectangular box.

First let's consider the case where $R$ is actually a cube, so all of its edges are the same common length, which we will call $a$.

If we consider just one of these edges, then the number of cubes we need to cover the edge is almost $a/k^{-1} = ak$. This is what it would be if the cubes fit perfectly into the edge, but there may be a little space leftover, so the number of cubes we need is surely no more than $ak + 2$, adding one for each endpoint of the edge.

Thus the number of cubes in a $(d-1)$-dimensional face is no more than the product of the lengths of all the $d-1$ edges: $$ \#\{\text{cubes in a face}\} \le (ak + 2)^{d-1} \le (a+1)^{d-1}k^{d-1}, \qquad {(2\le k).} $$ Now, there are $2d$ faces, so the number of cubes in $\mathcal Q'$ is no more than $2d(a+1)^{d-1}k^{d-1}$. Thus, if $2\le k$ and if $k$ is so large that $1/k < a$, then we have the desired result.

To apply this argument to a general rectangle, let $a$ be the length of the longest edge of the rectangle. Then it is clear that the rectangle $R$ is contained in a cube of edge length $a$. The number of cubes in $\mathcal Q'$ for the rectangle can be no more than that of the larger cube, which we know to be $O(k^{d-1})$. Hence there are $O(k^{d-1})$ cubes in $\mathcal Q'$ for the rectangle, as desired.