computational geometryとは何？わかりやすく解説 Weblio辞書

OR事典

索引トップ用語の索引ランキングカテゴリー

計算幾何学

読み方：けいさんきかがく
【英】：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事典」の他の用語

計算幾何：

立体射影組合せ最適化問題美術館監視問題計算幾何学記号摂動重み最小三角形分割領域探索

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

計算幾何学

(computational geometry から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/11 22:53 UTC 版)

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

脚注

^ 英: Combinatorial computational geometry または algorithmic geometry
^ 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
^ 英: Numerical computational geometry、machine geometry
^ 英: computer-aided geometric design、CAGD
^ 英: geometric modeling
^ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)

[続きの解説]

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

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「computational geometry」の例文・使い方・用例・文例

＜geometry).

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「computational geometry」を含む用語の索引
computational geometryのページへのリンク


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 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の元に提供されております。
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

computational geometryとは？わかりやすく解説

計算幾何学

概要

詳説

計算幾何学

「computational geometry」の例文・使い方・用例・文例

「computational geometry」の関連用語

computational geometryとは？ わかりやすく解説

計算幾何学

概要

詳説

計算幾何学

「computational geometry」の例文・使い方・用例・文例

「computational geometry」の関連用語

computational geometryとは？わかりやすく解説