計算幾何学とは?

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.

「OR事典」の他の用語
計算幾何:  記号摂動  極変換  区間木  計算幾何学  厳密計算法  最遠点対  最近点対

計算幾何学

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/01/27 04:58 UTC 版)

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


  1. ^ : Combinatorial computational geometry または algorithmic geometry
  2. ^ Franco P. Preparata、Michael 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)


「計算幾何学」の続きの解説一覧



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


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

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

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

計算幾何学のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



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

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2018 (社)日本オペレーションズ・リサーチ学会 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の元に提供されております。

©2018 Weblio RSS