New Upper Bounds in Klee’s Measure Problem

New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O (n^d / 2 n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on a new data structure, which is called an orthogonal partition tree. This structure has other applications as well.