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.
|Original language||English (US)|
|Number of pages||12|
|Journal||SIAM Journal on Computing|
|State||Published - 1991|
ASJC Scopus subject areas
- Computer Science(all)