Klee’s measure problem とは

計算幾何学では、Kleeの測度問題は、(多次元の)矩形範囲の和集合の尺度がいかに効率的に計算されるかを決定する問題である。ここで、d次元矩形範囲は、実数のd間隔のデカルト積であると定義され、これはRdのサブセットである。
この問題はVictor Kleeにちなんで命名された。Victory Kleeは、後で計算複雑性理論の意味で最適に効率的であることが示された区間の長さを計算するアルゴリズムを与えた(ケースd = 1)。 2次元矩形範囲の和集合の面積を計算する計算量は今も分かっているが、d≥3の場合は未解決の問題である。