  The KLEE'S MESURE of $n$ axis-parallel boxes in $\mathbb{R}^d$ is the volume
of their union. It can be computed in time within $O(n^{d/2})$ in the worst
case. We describe three techniques to boost its computation: one based on some
type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of
the structure of the input. The first technique benefits from instances where
the MAXIMA of the input is of small size $h$, and yields a solution running in
time within $O(n\log^{2d-2}{h}+ h^{d/2}) \subseteq O(n^{d/2}$). The second
technique takes advantage of instances where no $d$-dimensional axis-aligned
hyperplane intersects more than $k$ boxes in some dimension, and yields a
solution running in time within $O(n \log n + n k^{(d-2)/2}) \subseteq
O(n^{d/2})$. The third technique takes advantage of instances where the
\emph{intersection graph} of the input has small treewidth $\omega$. It yields
an algorithm running in time within $O(n^4\omega \log \omega + n (\omega \log
\omega)^{d/2})$ in general, and in time within $O(n \log n + n \omega ^{d/2})$
if an optimal tree decomposition of the intersection graph is given. We show
how to combine these techniques in an algorithm which takes advantage of all
three configurations.
