New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(nd/2 log 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 new data structure, which is called an orthogonal partition tree. This structure has order applications as well.
ASJC Scopus subject areas
- Computer Science(all)