組合せ計算幾何学の研究の主な目標は、点、線分、多角形、多面体などの基本的な幾何学オブジェクトで示される問題を解くための効率的なアルゴリズムとデータ構造を開発することである。 たとえば、最も近いペア問題を考えてみましょう。
- 平面上の n 個の点が与えられたとき、互いに最も小さい距離を持つ 2 つを求めよ。 このブルートフォース・アルゴリズムはO(n2)時間、つまり実行時間は点の数の二乗に比例する。 計算幾何学の古典的な成果は、O(n log n)を要するアルゴリズムを定式化したことである。 6835>
問題のクラス編集
計算幾何学の中心的な問題は、さまざまな基準に従って、さまざまな方法で分類されることがある。 6835>
Static problemsEdit
このカテゴリーの問題では、いくつかの入力が与えられ、対応する出力を構築または発見することが必要である。 このタイプの基本的な問題には次のようなものがある：
- 凸包． 点の集合が与えられたとき、すべての点を含む最小の凸多面体／多角形を求める。
- 線分の交差。
- ドロネーの三角測量
- ボロノイ図：与えられた線分の集合の間の交点を見つける。
- Linear programming
- Closest pair of points: 点の集合が与えられたとき、どの点が与えられた点に最も近いかによって空間を分割する。
- Farthest pair of points
- Largest empty circle: 点の集合が与えられたとき、その中心がそれらの凸包の内側にあり、どれも囲んでいない最大の円を求める。
- ユークリッド最短路。 ユークリッド空間（多面体障害物あり）において、2点を最短経路で結ぶ。 多角形が与えられたとき、その内部を三角形に分割する
- メッシュ生成
- 多角形に対するブール演算
このクラスの問題の計算量は、与えられた問題インスタンスを解くために必要な時間と空間（コンピュータメモリ）により見積もられます。
Geometric query problemsEdit
一般に幾何学的探索問題として知られている幾何学的探索問題では、入力は探索空間部分と問題インスタンスにわたって変化するクエリー部分の二つから構成されている。
いくつかの基本的な幾何学的クエリー問題は以下の通りである：
- 範囲検索：クエリー領域内の点の数を効率的に数えるために、点集合の前処理をすること。 空間をセルに分割したとき、クエリポイントがどのセルに位置するかを効率的に示すデータ構造を生成する
- Nearest Neighbor（ニアレストネイバー）。 点の集合を前処理して、どの点がクエリ点に最も近いかを効率的に見つける。
- レイトレーシング。
- Ray tracing: 空間内のオブジェクトのセットが与えられたとき、クエリの光線が最初に交差するオブジェクトを効率的に示すデータ構造を生成する。
探索空間が固定されている場合、このクラスの問題の計算複雑度は通常次のように見積もられる：
- で探索するデータ構造の構築に要する時間とスペース
- 問い合わせに対する応答の時間（および場合によっては追加のスペース）。
探索空間が変化する場合については、「動的問題」を参照。
動的問題編集
さらに別の主要クラスは動的問題で、目的は入力データの増分（入力幾何要素の追加や削除）のたびに繰り返し解を見つけるための効率的アルゴリズムを発見することである。 この種の問題に対するアルゴリズムは、典型的には動的なデータ構造を伴う。 計算幾何学問題のいずれかを、処理時間の増加を犠牲にして、動的な問題に変換することができる。 例えば、範囲検索問題は、点の追加および／または削除を提供することによって、動的範囲検索問題に変換されてもよい。 動的凸包問題は、動的に変化する点の集合に対して、例えば、凸包を追跡することである、すなわち。
このクラスの問題の計算複雑度は、次のように見積もられる：
- で検索されるデータ構造を構築するのに必要な時間と空間
- 検索空間の漸進的な変更後に検索されたデータ構造を修正する時間と空間
- 問い合わせに答える時間（および場合によっては余分な空間）。
VariationsEdit
問題によっては、文脈によってどちらかのカテゴリに属するものとして扱われることがある。 例えば、次のような問題を考えてみましょう。
- 多角形の中の点。
多くのアプリケーションでは、この問題は単発的なもの、つまり第1級に属するものとして扱われる。 例えば、コンピュータグラフィックスの多くの応用では、画面上のどの領域がポインタによってクリックされたかを見つけることが一般的な問題である。 しかし、アプリケーションによっては、問題のポリゴンは不変であるが、ポイントはクエリーを表す。 例えば、入力ポリゴンはある国の国境を表し、点は航空機の位置であり、航空機が国境を侵犯したかどうかを判断する問題である。 最後に、先に述べたコンピュータ・グラフィックスの例では、CADアプリケーションにおいて、変化する入力データはしばしば動的データ構造に格納され、これを利用してポイント・イン・ポリゴン問合せを高速化できる。
問合せ問題の文脈によっては、問合せの順序に関する妥当な期待があり、これを利用して、効率の良いデータ構造または計算複雑度の厳しい推定のいずれかを行うことも可能である。 例えば、いくつかのケースでは、単一のクエリではなく、N個のクエリのシーケンス全体の総時間のワーストケースを知ることが重要である。 償却分析 “も参照してください。