On the klee’s measure problem in small dimensions

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

6 Scopus citations


The Klee’s measure problem is to compute the volume of the union of a given set of n isothetic boxes in a d-dimensional space. The fastest currently known algorithm for this problem, developed by Overmars and Yap [6], runs in time O(nd/2 log n). We present an alternative simple approach with the same asymptotic performance. The exposition is restricted to dimensions three and four.

Original languageEnglish (US)
Title of host publicationSOFSEM 1998
Subtitle of host publicationTheory and Practice of Informatics - 25th Conference on Current Trends in Theory and Practice of Informatics, Proceedings
EditorsBranislav Rovan
PublisherSpringer Verlag
Number of pages8
ISBN (Print)3540652604, 9783540652601
StatePublished - Jan 1 1998
Externally publishedYes
Event25th Conference on Theory and Practice of Informatics, SOFSEM 1998 - Jasna, Slovakia
Duration: Nov 21 1998Nov 27 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th Conference on Theory and Practice of Informatics, SOFSEM 1998

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the klee’s measure problem in small dimensions'. Together they form a unique fingerprint.

Cite this