New upper bounds in Klee's measure problem

Mark H. Overmars, Chee Keng Yap

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

Abstract

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
Pages550-556
Number of pages7
ISBN (Print)0818608773, 9780818608773
DOIs
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

Overmars, M. H., & Yap, C. K. (1988). New upper bounds in Klee's measure problem. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 550-556). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21971