Abstract of Paper


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.