New upper bounds in Klee's measure problem

Mark H. Overmars, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution


New upper bounds are given for the measure problem of V. Klee (1977) that significantly improve the previous bounds for dimensions greater than 2. An O(nd2 log n, n) time-space upper bound to compute the measure of a set of n boxes in Euclidean d-space is obtained. The solution requires several novel ideas including application of the inclusion/exclusion principle, the concept of trellises, streaming, and a partition of d-space.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Number of pages7
ISBN (Print)0818608773, 9780818608773
StatePublished - 1988

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this