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:
“I candidly confess that I have ever looked on Cuba as the most interesting addition which could ever be made to our system of States. The control which, with Florida, this island would give us over the Gulf of Mexico, and the countries and isthmus bordering on it, as well as all those whose waters flow into it, would fill up the measure of our political well-being.”
—Thomas Jefferson (1743–1826)
“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)