計算・幾何学とは? わかりやすく解説

Weblio 辞書 > 固有名詞の種類 > 方式・規則 > 主義・方式 > 学問 > 学問 > 計算・幾何学の意味・解説 

計算幾何学

読み方けいさんきかがく
【英】:computational geometry

概要

幾何学的な問題を解くための基本的なアルゴリズム体系化をめざす学問分野. 1970年代から始まった若い分野であるが, アレンジメントボロノイ図計算をはじめ, すでに膨大なアルゴリズム蓄積されている.

詳説

 計算幾何学 (computational geometry) とは, 幾何的問題効率よく解くための基本アルゴリズム蓄積と体系化をめざす学問分野である. 計算幾何学という名称が初め使われたのは Shamos の学位論文 [1] だと言われている. 1970年代中頃生まれたこの分野は, その後急速に発展し, 1980年代中頃には相次いで標準的な教科書出版された [2, 3, 4].

 計算幾何学で扱う問題多岐に渡るが, 以下に示すのはその中でも最も基本的なのである.

 平面上に有限個の点が指定されたとき, どの点に最も近いかによって平面それぞれの点の勢力圏分割した図形ボロノイ図 (Voronoi diagram) といい, 最初に与えた点を生成元という. ボロノイ図自然界パターン解析, 地理的最適化など多く応用使われている. n\, 個の生成元ボロノイ図{\rm O}(n\log n)\, 計算量作ることができ, これが最適であることもわかっている. ボロノイ図は, 空間次元や距離を変えることによって多く種類のものが定義できる. 上に述べたのはその中の最も基本的なもので, 点ボロノイ図 (Voronoi diagram for points) とよばれている.

 空間の点の集合 X\, は, 「X\, 内の任意の 2 点を結ぶ線分X\, 含まれる」という性質満たすとき凸集合よばれる. 与えられた点の集合 S\, に対して, S\, を含む最小凸集合S\, 凸包 (convex hull) という. d\, 次元空間における n\, 個の点の集合 S\, 対す凸包は, d=2\, のとき {\rm O}(n\log n)\, 計算量で, d \geq 3\, のとき {\rm O}(n^{\lfloor d/2\rfloor})\, 計算量求めることができる. ただし \lfloor x \rfloor\, x\, 以下の最大整数を表す. また, これより小さ計算量では求められないこともわかっている.

 S\, 平面上に指定されn\, 個の点の集合とする. S\, 凸包内部を, S\, 属すすべての点を頂点使って三角形分割した図形を, S\, 張る三角形分割 (triangulation) という. S\, 張る三角形分割一般に通りもある. その中で, 点ボロノイ図双対図形として得られる三角形分割 (ドロネー図), 辺長の和が最小三角形分割 (重み最小三角形分割) などが, 比較ふっくらとした三角形多く含む分割であるためによく調べられている. 前者{\rm O}(n\log n)\, 計算量構成できるが, 後者構成する問題NP困難か否かわかっていない. 一方, 三角形の質は問わないで, どのような三角形使ってもよいからともかく S\, 張る三角形分割作りたいという場合でも{\rm O}(n\log n)\, より小さ計算量では作れないことがわかっている. その意味でもドロネー図重要な三角形分割である.

 d\, 次元空間n\, 個の超平面与えられたとき, それらの超平面互いに交差して空間分割する構造アレンジメント (arrangement) とよばれる. d=2\, 場合平面内の直線アレンジメントであり, 平面凸多角形分割した構造である. d=3\, 場合3 次元空間内の平面アレンジメントであり, 空間凸多面体分割される.

 (x,y,z)\, 座標系をもつ3次元空間において, z\, 軸に平行ではないn\, 平面作るアレンジメントA_n\, とする. A_n\, 空間いくつかの凸多面体分割するが, その境界となっているおのおのの凸多角形は, z\, 軸に平行な直線によって貫かれる順序によって, z\, 座標大きい方から1層目, 2層目, 等と層に分類することができる. これらの階層2次元ボロノイ図密接な関係がある [4].

 計算幾何学では, 各種幾何問題に対してそれを解く個別アルゴリズム追求するだけでなく, 異な幾何構造の間の関係を調べ, それをアルゴリズム開発利用する努力なされている. 異な幾何構造をつなぐための代表的道具一つ双対変換 (dual transformation) である. 最も素朴な双対変換平面上の直線 y=ax+b\, を点 (a,-b)\, 変換させるのである. この変換によって点は直線変換され, もとの平面での直線と点との接続関係双対変換施したあとも保たれる. このことを利用すると, たとえば平面上に指定されn\, 本の線分のすべてを通過する1本の直線求め問題 (串刺し問題) は, n\, 個のくさび形領域共通部分求め問題帰着される. このように変換によって問題扱いやすい別の問題帰着させる技術も計算幾何学では多数蓄積されている.



参考文献

[1] M. I. Shamos, Computational Geometry, Ph.D. Thesis, Department of Computer Science, Yale University, New Haven, 1978.

[2] F. P. Preparata and M. I. Shamos, Computational Geometry -An Introduction, Springer-Verlag, New York, 1985.

[3] 伊理正夫監修, 腰塚武志編集, 『計算幾何学と地理情報処理』, 共立出版, 1986. (第2版, 1993).

[4] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.


計算幾何学

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/01/18 16:30 UTC 版)

計算幾何学(けいさんきかがく、英語: computational geometry)は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。

概要

計算幾何学はコンピュータグラフィックスの発展、計算機支援のデザインや操作 (CAD/CAM) の研究分野としての側面を主な動機として展開されたが、計算幾何学における問題は、その多くが自然界における古典的な幾何学の問題である。

ほかに、計算幾何学の重要な応用は次のものがある。

ロボット工学
行動計画や問題の可視性
幾何学情報システム
幾何学的配置および探索、ルート選定
集積回路設計
集積回路の幾何学的設計と検証
計算機支援工学
数値制御機械のプログラミング

計算幾何学の主な分科には次のようなものがあげられる:

組合せ論的計算幾何学[1]
離散的な存在としての幾何学的対象を扱う。この主題における下敷きとなる基礎的な教科書は、1975年に初めてこの意味で「計算幾何学」という用語を用いた、Preparata と Shamos[2]である。
数値計算幾何学[3]、計算機支援幾何学的デザイン[4]、幾何学的モデリング[5]
実世界の物体を CAD/CAM システムにおける計算機計算に適した形で表現することを第一に扱う。この分科は画法幾何学の更なる発展形と見ることができ、しばしばコンピュータグラフィックスや CAD に関する分野の一部と考えられる。この意味で用語「計算幾何学」が使われるようになったのは1971年[6]からのことである。

組合せ論的計算幾何学

組合せ論的計算幾何学における研究の第一の目的は、(線分多角形多面体などのような)基本的な幾何学対象の言葉で述べられる問題の解決に対して、効果的なアルゴリズムデータ構造を開発することである。

これらの問題の中には、とても単純で計算機が出現するまではとても問題とは見なされていなかったようなものもある。例えば最近接点探索と呼ばれる、

平面上に与えられた n 個の点に対し、互いの距離がもっとも小さくなるような二点を求めよ。

という問題を考えよう。与えられた点の(n(n − 1)/2 個ある)全ての対に対してそれらの距離を計算すれば、最短の距離にある対を取り出すことができる。このブルート・フォースアルゴリズムはランダウの記号を使えば O(n2) 時間である(つまり、実行時間が点の数の自乗に比例する)。計算幾何学における古典的な結果として O(n log n) 時間だけ掛かるアルゴリズムが定式化された。確率的アルゴリズムでは O(n) であることが期待され、同様に決定性アルゴリズムでは O(n log log n) 時間を持つことが発見された。

計算幾何学では、アルゴリズムが一千万や一億といったようなたくさんの点を含む非常に巨大なデータ集合の上で用いられることを想定して、計算量を非常に重要視する。巨大なデータ集合に対し、 O(n2) と O(n log n) との違いは、計算が数日掛かるか数秒で終わるかというくらいのはっきりした違いを生むのである。

問題の分類

組合せ論的計算幾何学における中心的な問題に関して、いくつかの判定法に従った異なる方法による分類が可能である。一般的には以下のような分類が区別される。

静的問題

これに分類される問題は、いくつか入力が与えられた状態で、それに対応する出力を構築または計算することが要求される。この種の基本的な問題として

  • 凸包: 与えられた点の集合に対して、それらを全て含む最小の凸多角形凸集合を計算する問題。ギフト包装法など。
  • 線分交叉問題: 与えられた線分の集合に対して、それらの交点を求める問題。
  • ドロネー三角形分割
  • ボロノイ図: 与えられた点の集合に対して、それらの中で最も近い点に代表される部分に属するように空間を分割する問題。
  • 線型計画問題
  • 最近接点探索: 与えられた点の集合に対して、その中で最も互いの距離が短いふたつを選び出す問題。
  • ユークリッド的最短経路問題: (多面体の障害物がある)ユークリッド空間において、与えられた二点を最短経路で結ぶ問題。
  • 多角形の三角形分割: 与えられた多角形を、その内部にある三角形に分割する問題。

などが挙げられる。この種の問題に対する組合せ論的な計算量は、与えられた問題事例が要求する時間と空間(計算機のメモリ)によって評価される。

幾何学的問合せ問題

一般には幾何学的探索問題として知られる幾何学的問合せ問題において、入力は探索空間と問合せ(クエリ)の二つの部分からなり、それらは問題事例に応じてさまざまなものがある。探索空間はふつう、複数の問合せに効果的に応答することができるように、前処理されている必要がある。

基本的な幾何学的問合せ問題としては、

  • 範囲探索: 点の集合を前処理して、要求された領域の内側にある点の数を効果的に数えられるように整列する。
  • 点配置: 空間のセル分割が与えられたとき要求された点がどのセルに配置されるかを効果的に解答できるようなデータ構造を導出する問題。
  • 最近接近傍探索: 点の集合を前処理して、要求された点に最も近い点を効果的に見つけられるように並べ替える。
  • レイ・トレーシング: 空間内の物体の集合が与えられたとき、要求された半直線が最初にどの物体と交わるかを解答する効果的なデータ構造を求める問題。

などが挙げられる。探索空間を固定するとき、この類の問題に対する計算量は通常

  • 探索に必要なデータ構造を構築するの必要な時間と空間、
  • 問合せに応答するまでの時間(と場合によっては余分の空間)

によって評価される。探索空間を変更することが許される場合については後述の#動的問題を参照。

動的問題

もうひとつ大きな分類として動的問題があり、それは(入力する幾何学的要素を加えたり除いたりするような)入力の逐次変更に追随して繰り返し解を求める効果的なアルゴリズムの発見を目的とする。この種の問題に対するアルゴリズムは普通、動的データ構造を伴う。計算幾何学的な問題はどれも動的問題に作り変えることができる。例えば範囲探索問題は与える点を増減させることを考えることによって動的範囲探索問題に変形される。動的凸包問題は、たとえば(入力点を増減させるような)点集合の動的な変化に対しての、凸包の変化の様子を追う問題である。

この種の問題の計算量は

  • 探索に用いるデータ構造の構築に必要な時間と空間、
  • 探索されたデータ構造の探索空間における逐次変更に伴う修正に掛かる時間と空間、
  • 要求に解答するための時間(と余分な空間)

によって評価される。

変種

問題の中には、文脈によってどちらのカテゴリーにも属するものとして扱わなければならないようなものもある。例えば次の

  • Point in polygon: 点が与えられた多角形の内側にあるか外側にあるかどうかを決定せよ。

という問題を考えよう。多くの応用では単発のものとして扱って、静的な問題に属することになるだろう。たとえばコンピュータグラフィックスに関する応用の多くでは、マウスカーソルで画面のどの領域がクリックされたか知るというようなことがよくある問題である。しかし、応用の中には問における多角形は不変だが、点は問合せを表すようなものもある。例えば、入力する多角形が国境を表し、点が航空機の位置を表していて、航空機が領空侵犯しているかどうかを判定せよという問題などである。最後に、コンピュータグラフィックスについて上で述べた例に関して、CAD ソフトは入力データの変化を、点が多面体の中にあるかの問合せのスピードアップに活用するために、動的データ構造として格納する。

問合せ問題の文脈には、効果的なデータ構造や精緻な計算量評価に活用することができる、問合せの列の存在を期待するほうが合理的というようなものもある。たとえば、個々の問合せのどれに一番時間が掛かるかを知るよりも、一続きの複数の問合せの全体にかかる合計時間が最悪のものを知ることのほうが重要であるというような場合があるかもしれない。「償却解析」("amortized analysis") も参照。

数値的計算幾何学

この分科は幾何学的モデリング計算機支援幾何学デザイン (CAGD) としても知られる。

中核となる問題は曲線や曲面のモデリングと表現である。

ここでの基本的な道具はベジエ曲線スプライン曲線・スプライン曲面のような曲線のパラメータ表示および曲面のパラメータ表示である。非パラメトリックな手法としてはレベル集合がある。

応用分野には、造船、航空、自動車製品などが含まれる。現代における計算機の遍在性と能力が意味するのは香水ビンやシャンプーのボトルでさえ、1960年代の造船技師では考えられないような手法を用いてデザインを行っているということなのである。

脚注

  1. ^ : Combinatorial computational geometry または algorithmic geometry
  2. ^ Franco P. PreparataMichael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3 
  3. ^ : Numerical computational geometrymachine geometry
  4. ^ : computer-aided geometric design、CAGD
  5. ^ : geometric modeling
  6. ^ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)

関連項目

参考文献

関連文献

雑誌

組合せ論的計算幾何学

以下は、出版された大手の幾何学的アルゴリズムに関する研究誌の一覧である。見るからに計算幾何学をはっきりと専門とする雑誌を優先し、計算機科学一般を目的とした雑誌やコンピュータグラフィックスに関する雑誌の幾何学的な出版物の割合は減らしてあることに注意されたい。

外部リンク


計算幾何学

出典:『Wiktionary』 (2021/11/30 04:32 UTC 版)

名詞

計算 幾何学けいさんきかがく

  1. (情報技術, 幾何学) 電子計算機幾何学問題を(近似的に)解くアルゴリズム考え学問

参照




計算・幾何学と同じ種類の言葉


固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「計算・幾何学」の関連用語

計算・幾何学のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



計算・幾何学のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの計算幾何学 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Text is available under Creative Commons Attribution-ShareAlike (CC-BY-SA) and/or GNU Free Documentation License (GFDL).
Weblioに掲載されている「Wiktionary日本語版(日本語カテゴリ)」の記事は、Wiktionaryの計算幾何学 (改訂履歴)の記事を複製、再配布したものにあたり、Creative Commons Attribution-ShareAlike (CC-BY-SA)もしくはGNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS