Adaptive Computation of the Klee's Measure in High Dimensions

Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma

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 tec…