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:
“Who can measure the advantages that would result if the magnificent abilities of these women could be devoted to the needs of government, society and home, instead of being consumed in the struggle to obtain their birthright of individual freedom? Until this be gained we can never know, we can not even prophesy the capacity and power of women for the uplifting of humanity.”
—Susan B. Anthony (1820–1906)
“A curious thing about the ontological problem is its simplicity. It can be put in three Anglo-Saxon monosyllables: ‘What is there?’ It can be answered, moveover, in a word—‘Everything.’”
—Willard Van Orman Quine (b. 1908)