  We propose a new approach to the computation of the hypervolume indicator,
based on partitioning the dominated region into a set of axis-parallel
hyperrectangles or boxes. We present a nonincremental algorithm and an
incremental algorithm, which allows insertions of points, whose time
complexities are $O(n^{\lfloor \frac{p-1}{2} \rfloor+1})$ and $O(n^{\lfloor
\frac{p}{2} \rfloor+1})$, respectively. While the theoretical complexity of
such a method is lower bounded by the complexity of the partition, which is, in
the worst-case, larger than the best upper bound on the complexity of the
hypervolume computation, we show that it is practically efficient. In
particular, the nonincremental algorithm competes with the currently most
practically efficient algorithms. Finally, we prove an enhanced upper bound of
$O(n^{p-1})$ and a lower bound of $\Omega (n^{\lfloor \frac{p}{2}\rfloor} \log
n )$ for $p \geq 4$ on the worst-case complexity of the WFG algorithm.
