New upper bounds in Klee's measure problem

Mark H. Overmars, Chee Keng Yap

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)1034-1045
Number of pages12
JournalSIAM Journal on Computing
Issue number6
StatePublished - 1991

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'New upper bounds in Klee's measure problem'. Together they form a unique fingerprint.

Cite this