クレーの測度問題

計算幾何学において、クレーの測度問題とは、 （多次元の）長方形範囲の和集合の測度をいかに効率的に計算できるかを決定する問題である。ここで、 d次元の長方形範囲は、 R ^dのサブセットである実数のd個の区間の直積として定義される。

この問題は、区間の和集合の長さ（d = 1 の場合）を計算するアルゴリズムを提案したヴィクトール・クレーにちなんで名付けられました。このアルゴリズムは、後に計算複雑性理論の意味で最適に効率的であることが示されました。2 次元の長方形範囲の和集合の面積を計算する計算複雑性も現在ではわかっていますが、d ≥ 3の場合は未解決の問題のままです。

1977 年、ヴィクトール・クレーは次のような問題を考えました。実数直線上のn 個の 区間の集合が与えられた場合、それらの和集合の長さを計算します。次に、彼はこの問題を計算複雑度(または「実行時間」)で解くアルゴリズムを提示しました。このステートメントの意味については、Big O 表記法を参照してください。区間のソートに基づくこのアルゴリズムは、後にマイケル・フレッドマンとブルース・ワイデ (1978) によって最適であることが 示されました。${\displaystyle O(n\log n)}$

1977 年後半、ジョン・ベントレーはこの問題の 2 次元類似問題を考えた。n個の 長方形の集合が与えられたとき、それらの和集合の面積を求めるという問題である。彼はまた、問題をn 個の1次元問題に簡約することに基づいた、現在ベントレーのアルゴリズムとして知られる複雑性アルゴリズムも得た。これは、領域を垂直線で掃引することによって行われる。この方法を使用すると、和集合自体を明示的に構築しなくても、和集合の面積を計算できる。ベントレーのアルゴリズムは現在では最適であることも知られており (2 次元の場合)、コンピュータ グラフィックスなどの分野で使用されている。 ${\displaystyle O(n\log n)}$

これら 2 つの問題は、より一般的な質問の 1 次元および 2 次元の場合です。n d 次元の長方形範囲のコレクションが与えられた場合、 それらの和集合の測度を計算します。この一般的な問題は、クレーの測度問題です 。

d次元の場合に一般化すると、ベントレーのアルゴリズムの実行時間は になります。これは最適ではないことが判明しました。なぜなら、 d次元の問題をn ( d-1 ) 次元の問題に分解するだけで、それらのサブ問題をさらに分解しないからです。1981 年に、Jan van Leeuwenと Derek Wood は、動的四分木を使用することで、このアルゴリズムの実行時間をd ≥ 3の場合に まで改善しました。 ${\displaystyle O(n^{d-1}\log n)}$${\displaystyle O(n^{d-1})}$

1988 年、マーク・オーバーマルスとチー・ヤップはd ≥ 3のアルゴリズムを提案しました。彼らのアルゴリズムは、 kd ツリーに似た特定のデータ構造を使用して、問題を 2 次元コンポーネントに分解し、それらのコンポーネントを効率的に集約します。2 次元の問題自体は、トレリス構造を使用して効率的に解決されます。ベントレーのアルゴリズムよりも漸近的には高速ですが、そのデータ構造は大幅に多くのスペースを使用するため、 nまたはdが大きい問題でのみ使用されます。1998 年、ボグダン・クレバスは、 dが 3 または 4である一般的な特殊なケースに対して、同じ漸近実行時間でより単純なアルゴリズムを提案しました。 ${\displaystyle O(n^{d/2}\log n)}$

2013 年、Timothy M. Chan は、動的データ構造の必要性を回避し、対数係数を排除したより単純なアルゴリズムを開発し、d ≥ 3 の既知の最速実行時間を に短縮しました。 ${\displaystyle O(n^{d/2})}$

任意のdの唯一の既知の下限は であり、この実行時間を持つ最適なアルゴリズムはd =1 およびd =2 の場合に知られています。Chan アルゴリズムはd ≥ 3に対しての上限を提供するため、d ≥ 3 の場合、より高速なアルゴリズムが可能かどうか、またはより厳しい下限が証明できるかどうかは未解決の問題です。特に、アルゴリズムの実行時間がdに依存しなければならないかどうかは未解決のままです。さらに、特殊なケース (たとえば、入力座標が制限された範囲内の整数である場合) を処理できるより高速なアルゴリズムがあるかどうかという問題も未解決のままです。 ${\displaystyle \Omega (n\log n)}$${\displaystyle O(n^{d/2})}$

1D Klee の測度問題 (区間の和集合) は次のように解くことができます。ここでp はすべての区間を突き通すために必要な貫通点の数を表します^[1] (共通点によって貫通された区間の和集合は、極値を計算することで線形時間で計算できます)。パラメータpは入力構成に依存する適応パラメータであり、貫通アルゴリズム^{[2] は}Klee の測度問題に対する適応アルゴリズムを生成します。 ${\displaystyle O(n\log p)}$

• 凸体積近似、凸体の効率的なアルゴリズム

• クリー、ビクター(1977)、「 の尺度は未満のステップで計算できるか?」アメリカ数学月刊誌、84 (4): 284–285、doi :10.2307/2318871、JSTOR  2318871、MR  0436661${\displaystyle \cup [a_{i},b_{i}]}$${\displaystyle O(n\log n)}$。
• Bentley, Jon L. (1977)、「Klee の長方形問題に対するアルゴリズム」、未発表ノート、カーネギーメロン大学コンピュータサイエンス学部。
• Fredman, Michael L. ; Weide, Bruce (1978)、「の測定を計算する複雑さ」、Communications of the ACM、21 (7): 540–544、doi : 10.1145/359545.359553、MR  0495193、S2CID  16493364${\displaystyle \cup [a_{i},b_{i}]}$。
• van Leeuwen, Jan ; Wood, Derick (1981)、「 d空間における長方形範囲の測定問題」、Journal of Algorithms、2 (3): 282–300、doi :10.1016/0196-6774(81)90027-4、hdl : 1874/15897、MR  0632450。
• Overmars, Mark H. ; Yap, Chee-Keng (1991)、「Klee の測度問題における新しい上限」、SIAM Journal on Computing、20 (6): 1034–1045、doi :10.1137/0220065、hdl : 1874/16614、MR  1135747。
• Chlebus, Bogdan S. (1998)、「小さな次元における Klee の測度問題について」、情報科学の理論と実践の最新動向に関する第 25 回会議の議事録 (SOFSEM-98)、コンピュータ サイエンスの講義ノート、第 1521 巻、ベルリン: Springer-Verlag、pp. 304–311、doi :10.1007/3-540-49477-4_22、ISBN 978-3-540-65260-1。
• Chan, Timothy M. (2013)、「Klee の測度問題の簡単な解説」、第 54 回 IEEE コンピュータサイエンス基礎シンポジウム (FOCS) の議事録(PDF)、pp. 410–419、CiteSeerX  10.1.1.643.26、doi :10.1109/FOCS.2013.51、ISBN 978-0-7695-5135-7、S2CID  11648588。

• Franco P. PreparataおよびMichael I. Shamos (1985)。計算幾何学(Springer-Verlag、ベルリン)。
• ジェフ・エリクソン教授の計算幾何学における未解決問題リストからの「クレーの測度問題」。(2005 年 11 月 8 日にアクセス。最終更新日は 1998 年 7 月 31 日。)