On the Klee's Measure Problem in Small Dimensions
by Bogdan S. Chlebus
Abstract:
The Klee's measure problem is to compute the volume of the union of a given set of $n$ isothetic boxes in a $d$-dimensional space (their edges are parallel to the coordinate axes). The fastest currently known algorithm for this problem, developed by Overmars and Yap, runs in time $O(n^{d/2}\log n)$. We present an alternative simple approach with the same asymptotic performance. The exposition is restricted to dimensions three and four.