In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a cartesian product of d intervals of real numbers, which is a subset of Rd.
The problem is named after Victor Klee, who gave an algorithm for computing the length of a union of intervals (the case d = 1) which was later shown to be optimally efficient in the sense of computational complexity theory. The computational complexity of computing the area of a union of 2-dimensional rectangular ranges is now also known, but the case d ≥ 3 remains an open problem.
Read more about Klee's Measure Problem: History and Algorithms, Current Status
Famous quotes containing the words measure and/or problem:
“Poetry is emotion put into measure. The emotion must come by nature, but the measure can be acquired by art.”
—Thomas Hardy (1840–1928)
“The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
—Frank Pittman (20th century)