組合せ論的計算幾何学

ウィキペディア小見出し辞書

組合せ論的計算幾何学

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/19 02:37 UTC 版)

「計算幾何学」の記事における「組合せ論的計算幾何学」の解説

離散的な存在としての幾何学的対象を扱う。この主題における下敷きとなる基礎的な教科書は、1975年に初めてこの意味で「計算幾何学」という用語を用いた、Preparata と Shamosである。

組合せ論的計算幾何学

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/19 02:37 UTC 版)

「計算幾何学」の記事における「組合せ論的計算幾何学」の解説

以下は、出版された大手の幾何学的アルゴリズムに関する研究誌の一覧である。見るからに計算幾何学をはっきりと専門とする雑誌を優先し、計算機科学一般を目的とした雑誌やコンピュータグラフィックスに関する雑誌の幾何学的な出版物の割合は減らしてあることに注意されたい。 en:ACM Computing Surveys en:ACM Transactions on Graphics en:Acta Informatica en:Advances in Geometry en:Algorithmica en:Ars Combinatoria en:Computational Geometry: Theory and Applications en:Communications of the ACM en:Computer Graphics and Applications en:Computer Graphics World en:Discrete & Computational Geometry en:Geombinatorics en:Geometriae Dedicata en:IEEE Transactions on Graphics en:IEEE Transactions on Computers en:IEEE Transactions on Pattern Analysis and Machine Intelligence en:Information Processing Letters en:International Journal of Computational Geometry and Applications en:Journal of Combinatorial Theory, series B en:Journal of the ACM en:Journal of Algorithms en:Journal of Computer and System Sciences Management Science Pattern Recognition en:Pattern Recognition Letters en:SIAM Journal on Computing en:SIGACT News; featured the "Computational Geometry Column" by Joseph O'Rourke en:Theoretical Computer Science en:The Visual Computer

組合せ論的計算幾何学

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/19 02:37 UTC 版)

「計算幾何学」の記事における「組合せ論的計算幾何学」の解説

組合せ論的計算幾何学における研究の第一の目的は、（点、線分、多角形、多面体などのような）基本的な幾何学対象の言葉で述べられる問題の解決に対して、効果的なアルゴリズムとデータ構造を開発することである。 これらの問題の中には、とても単純で計算機が出現するまではとても問題とは見なされていなかったようなものもある。例えば最近接点探索と呼ばれる、 平面上に与えられた n 個の点に対し、互いの距離がもっとも小さくなるような二点を求めよ。 という問題を考えよう。与えられた点の（n(n − 1)/2 個ある）全ての対に対してそれらの距離を計算すれば、最短の距離にある対を取り出すことができる。このブルート・フォースアルゴリズムはランダウの記号を使えば O(n2) 時間である（つまり、実行時間が点の数の自乗に比例する）。計算幾何学における古典的な結果として O(n log n) 時間だけ掛かるアルゴリズムが定式化された。確率的アルゴリズムでは O(n) であることが期待され、同様に決定性アルゴリズムでは O(n log log n) 時間を持つことが発見された。 計算幾何学では、アルゴリズムが一千万や一億といったようなたくさんの点を含む非常に巨大なデータ集合の上で用いられることを想定して、計算量を非常に重要視する。巨大なデータ集合に対し、 O(n2) と O(n log n) との違いは、計算が数日掛かるか数秒で終わるかというくらいのはっきりした違いを生むのである。