Loading article…
計算幾何学は、幾何学の観点から表現できるアルゴリズムの研究に特化したコンピュータ科学の一分野です。計算幾何学アルゴリズムの研究から純粋に幾何学的な問題が生じる場合もあり、そのような問題も計算幾何学の一部とみなされます。現代の計算幾何学は比較的新しい分野ですが、その歴史は古代にまで遡る、最も古いコンピュータ分野の一つです。
計算複雑性は計算幾何学において中心的な概念であり、数千万または数億もの点を含む非常に大規模なデータセットにアルゴリズムを適用する場合には、実用上大きな意味を持つ。このようなデータセットの場合、O ( n² )とO ( n log n )の違いは、計算時間の数日と数秒の違いにまで及ぶ可能性がある。
計算幾何学が学問分野として発展した主な原動力は、コンピュータグラフィックスとコンピュータ支援設計・製造（CAD / CAM）の進歩であったが、計算幾何学における多くの問題は古典的な性質のものであり、数学的可視化から生じる可能性がある。
計算幾何学のその他の重要な応用分野としては、ロボット工学（動作計画や視認性の問題）、地理情報システム（GIS）（幾何学的位置特定と検索、経路計画）、集積回路設計（IC形状設計と検証）、コンピュータ支援エンジニアリング（CAE）（メッシュ生成）、コンピュータビジョン（3D再構成）などが挙げられる。
計算幾何学の主な分野は以下のとおりです。
計算幾何学のアルゴリズムのほとんどは電子計算機向けに開発されてきた（そして開発され続けている）が、一部のアルゴリズムは非従来型のコンピュータ（例えば光コンピュータ[ 3 ]）向けに開発された。
組み合わせ計算幾何学の研究の主な目的は、点、線分、多角形、多面体などの基本的な幾何学的オブジェクトで表現された問題を解決するための効率的なアルゴリズムとデータ構造を開発することです。
これらの問題の中には、コンピュータが登場するまで問題として認識されなかったほど単純なものもある。例えば、最も近いペアの問題を考えてみよう。
すべての点のペア間の距離を計算し、そのペアの数をn ( n − 1)/2とすると、距離が最小のペアを選択することができます。この総当たりアルゴリズムはO ( n 2 ) の時間、つまり点の数の二乗に比例する実行時間を要します。計算幾何学における古典的な成果は、O ( n log n )の時間を要するアルゴリズムの定式化でした。期待時間がO ( n ) のランダム化アルゴリズム[ 4 ]や、O ( n log log n ) の時間を要する決定論的アルゴリズム[ 5 ]も発見されています。
計算幾何学における主要な問題は、様々な基準に基づいて、異なる方法で分類することができる。以下に、一般的な分類を区別することができる。
このカテゴリーの問題では、何らかの入力が与えられ、それに対応する出力を構築または求める必要があります。このタイプの基本的な問題には、次のようなものがあります。
この種の問題における計算複雑度は、与えられた問題インスタンスを解決するために必要な時間と空間（コンピュータメモリ）によって推定される。
幾何学的クエリ問題（一般に幾何学的探索問題とも呼ばれる）では、入力は探索空間部分とクエリ部分の2つの部分から構成され、クエリ部分は問題インスタンスごとに変化します。探索空間は通常、複数のクエリに効率的に応答できるように前処理する必要があります。
いくつかの基本的な幾何学的クエリ問題は次のとおりです。
探索空間が固定されている場合、この種の問題の計算複雑度は通常、次のように推定されます。
探索空間が変化することが許される場合については、§ 動的問題を参照してください。
もう一つの主要な分類は動的問題であり、その目的は入力データの増分変更（入力幾何学的要素の追加または削除）のたびに、解を繰り返し見つけるための効率的なアルゴリズムを見つけることです。この種の問題のアルゴリズムは、通常、動的データ構造を伴います。計算幾何学の問題は、処理時間の増加という代償を伴うものの、動的問題に変換できます。たとえば、範囲探索問題は、点の追加や削除を可能にすることで、動的範囲探索問題に変換できます。動的凸包問題は、入力点が挿入または削除されている間、動的に変化する点の集合などに対して、凸包を追跡することです。
この種の問題の計算複雑度は、以下のように推定されます。
状況によっては、問題がどちらのカテゴリーにも属するものとして扱われる場合がある。例えば、次の問題を考えてみよう。
多くのアプリケーションでは、この問題は単発的な問題、つまり第一のクラスに属する問題として扱われます。例えば、コンピュータグラフィックスの多くのアプリケーションでは、画面上のどの領域がポインタによってクリックされたかを検出することが一般的な問題です。しかし、一部のアプリケーションでは、対象となるポリゴンは不変である一方、ポイントはクエリを表します。例えば、入力ポリゴンが国の国境を表し、ポイントが航空機の位置を表している場合、問題は航空機が国境を越えたかどうかを判断することです。最後に、前述のコンピュータグラフィックスの例では、CADアプリケーションでは、変化する入力データが動的なデータ構造に格納されることが多く、これを利用してポリゴン内のポイントのクエリを高速化することができます。
クエリ問題の中には、クエリの順序に関して合理的な予測が可能な場合があり、これは効率的なデータ構造の構築や、より厳密な計算複雑度推定に活用できます。例えば、単一のクエリではなく、 N個のクエリのシーケンス全体の合計時間の最悪ケースを知ることが重要な場合もあります。償却分析も参照してください。
この分野は、幾何モデリングおよびコンピュータ支援幾何設計（CAGD）としても知られています。
中心的な課題は、曲線と曲面のモデリングと表現である。
ここで最も重要なツールは、ベジェ曲線、スプライン曲線、スプライン曲面などのパラメトリック曲線とパラメトリック曲面です。重要なノンパラメトリック手法としては、レベルセット法があります。
計算幾何学の応用分野には、造船、航空機、自動車産業などが含まれる。
以下は、幾何アルゴリズムに関する研究論文を掲載している主要な学術誌の一覧です。計算幾何学に特化した学術誌が登場したことで、一般的なコンピュータサイエンスやコンピュータグラフィックスの学術誌における幾何関連の論文の割合が減少していることにご留意ください。