'''【めたひゅーりすてぃくす (metaheuristics)】'''

=== 概要 ===
組合せ最適化問題において, 遺伝アルゴリズム, アニーリング法, タブー探索といった発見的な探索を行う手法を総合した枠組. 暫定解に対し局所探索によって解の更新を行うが, 局所最適解に捕捉されることを防ぐための工夫を付加するというのが基本的な考え方である. 一般に最適性は保証できないが, 少ない計算時間で質の良い解を求めることができる場合が多いので極めて実用性が高く, 様々な問題への応用がなされている.

=== 詳説 ===
　[[メタヒューリスティクス]] (metaheuristics) とは組合せ最適化問題に対しての, 発見的解法の枠組みであり, 従来の数理的, 分析的手法に基づく厳密解法に対し, ある暫定解からより良い解を発見的に探索するための方法論である. 1) 個々の問題の性質に依拠しないより包括的な枠組みである, 2) 最適解を求めることではなく, より良い解を現実的な時間で求めることを目的とする, といった特徴が挙げられる. メタヒューリスティクスに含まれる多くの手法は局所探索法 (local search) を元にしているが, 局所最適解で探索が終了してしまうという欠点を補うためのさまざまな工夫がなされている[7].

　[[多スタート局所探索]] (multi start local search) は適当な方法で生成した初期解からの局所探索法を繰り返し行うことにより, 改善された局所最適解を求めるものである.

　[[可変近傍法]] (variable neighborhood search) は複数の近傍を定義し, 暫定解（それまでに得られた最善解）に対しある近傍から一つ初期解を選択し, その解に対して局所探索法を適用するという手順を繰り返す. この反復において暫定解が更新されたか否かによって初期解を選択するための近傍を変える点に特徴がある.

　[[アニーリング法]] (simulated aneealing) は局所探索法の実行過程に確率的な振る舞いを加え局所最適解に陥らないようにしたアルゴリズムであり, Kirkpatrickらによって提案された [2]. アニーリング法では改悪の方向への移行を確率<math>P\, </math>で受け入れる. <math>P\, </math>は温度<math>t\, </math>と呼ばれる制御パラメータを含む関数で定義され, 目的関数が改悪される度合が大きくなれば小さくなるように定義される. 一般に用いられるのは, 変更にともなう目的関数値の変化量を<math>\Delta \, </math>(改悪ならば正、改良ならば負の値をとる)とすると,

<table align="center">
<tr>
<td><math>P=\left\{\begin{array}{l}
1,\;\Delta\le 0\\
\exp (-\Delta /t ),\Delta >0
\end{array}\right.</math>
</td>
</tr>
</table>

と定義される. パラメータ<math>t\, </math>は最初は大きな値に設定されるが、その後<math>t\, </math>を徐々に小さくすることによって, 探索の初期の段階では広い領域を探索し, 後期では探索が最適解に落ち着くことをねらっている.

　[[タブー探索]]　(tabu search)　は局所探索法において局所最適解から脱出するため, 近傍内の最良解（改悪解であっても）へ移行するという操作を加えたものである [3, 4] . 一つの局所最適解とその近傍のみの移行という繰り返しを避けるために, 現在までの移行の履歴を保持し, 移行に制約を設ける. この制約をタブーという. またタブーにより良い局所最適解への移行を妨げる場合があるのでタブー保有期間と呼ばれる一定期間を経るとタブーは解消される. これにより局所最適解に陥ることなく広範囲の解を探索することが可能になる.

　[[遺伝アルゴリズム]] (genetic algorithm) は生物の形質遺伝による進化を組合せ最適化問題における解の進化, すなわち目的関数値を向上させることに利用した解法である [6]. まず候補解を記号列として表現したものを遺伝子と名付け, これらの遺伝子からなる集団に対し1) 次世代に子孫を残す解を選択し (選択), 2) <math>2\, </math>つの親の遺伝子より子の遺伝子を生成し (交叉), 3) 遺伝子の一部を一定の確率で変化させ (突然変異), 4) 劣っている解は集団より除去する (淘汰), という操作を繰り返し行う. 交叉において遺伝子の特徴がどのように次の世代に遺伝していくかということは[[スキーマ定理]] (scheme theorem) によって確率的に示されている [5]. ここでスキーマ<math>H\, </math>とは遺伝子を2進数で表現したときの部分列であり, その次元を<math>o(H)\, </math>, 定義長を<math>\delta(H)\, </math>とし, <math>m(H,t)\, </math>を次世代<math>t\, </math>でスキーマ<math>H\, </math>を含む個体の数, <math>f(H)\, </math>スキーマ<math>H\, </math>を含む個体の適応度の平均値, <math>\overline{f}(t)\, </math>を世代<math>t\, </math>での個体の平均適応度とすると

<center>
<math>\begin{array}{lll}
m(H,t+1) &\geq& m(H,t)f(H)
\{1-p_c\delta(H)/(l-1)\}(1-p)^{o(H)}/\overline{f}(t) \\
&\approx& m(H,t)f(H)\{1-p_c\delta(H)/(l-1)-po(H)\}/\overline{f}(t)
\end{array}\, </math>
</center>

が成立する.

　遺伝アルゴリズムは[[進化的計算]] (evolutionary computation), 進化的プログラミング (evolutionary programming) といった生物の遺伝, 進化の過程を模倣して最適化問題における最適解を探索するという枠組みの中のひとつであり、さらには[[人工生命]] (artificial life) という生命システムをコンピュータでシミュレートする研究との関連においても注目されている.

----
'''参考文献'''

[1] G. Hansen and N. Mladenovic, "An Introduction to Variable Depth Search," in ''Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization'', S. Voss, eds., Kluwer Academic Publishers, 1998.

[2] S. Kirkpatrick, C. D. Gellat and M. P. Vecchi, "Optimization by Simulated Annealing," ''Science'', '''220''' (1983), 671-680.

[3] F. Glover, "Tabu Search I," ''ORSA Journal on Computing'', '''1''' (1989), 190-206.

[4] F. Glover, "Tabu Search II," ''ORSA Journal on Computing'', '''2''' (1989), 4-32.

[5] D. E. Goldberg, ''Genetic Algorithms in Search, Optimization, and Machine Learning'', Addison-Wesley, 1989.

[6] J. H. Holland, ''Adaptation in Natural and Artificial Sytems'', University of Michigan Press, 1975.

[7] 柳浦睦憲, 茨木俊秀, 「組合せ最適化」, 朝倉書店, 2001.

[[category:近似・知能・感覚的手法|めたひゅーりすてぃくす]]

ORWiki:ORWikiについて

2008-04-15T09:18:27Z

Imahori:

== 刊行にあたって ==
<p style="text-align:right;">
OR事典編集委員長<BR>
青木　利晴
</p>

　1957（昭和32) 年に創立された
[https://orsj.org/ 日本オペレーションズ・リサーチ（OR）学会]
は、今年6月に創立50周年という大きな節目を迎えました。これを記念して今春より数々の事業を実施していますが、その一つとして「ＯＲ事典」の改訂を行っています。初版は１９７５年に刊行し、１９９７年の創立４０周年には改訂版をＣＤ－ＲＯＭで提供いたしましたが、今回は創立５０周年記念事業として、改訂とともに新たにインターネットでの公開を実現いたしました。

　さて「知の世紀」といわれる21世紀に入った今、新たな時代環境の中で本学会も大きな変化を求められています。本学会は、これまでに築いてきた基盤の上に立って、今後とも発展し続けるように、新たなOR活用分野・研究手法の開拓、広報・研究普及活動の更なる拡充による社会への貢献、国際化の推進とアジア地域との連携などの課題について重点的に取り組み、真に役立つＯＲの研究・実践に努力を積み重ねてまいります。このような時期に「ＯＲ事典」を新たに編集し刊行することは、きわめて意義深いことだと思います。

　今回のＯＲ事典編集作業の結果、[[基礎編：大項目一覧|基礎編]]、
[[用語編]]に関してはＰＤＦベースから、ＷＩＫＩを使った方式に変換し、
より柔軟な使い方ができるようになりました。基礎編の見出し項目としては２８項目を追加、４項目を削除、用語は３００語が追加されました。
[[事例編]]については、「[https://orsj.org/wp-content/or-archives50/ ＯＲアーカイブ集]」より，事例に関する論文等を分類整理しました。
[http://www.ozsons.com/ORstory/ 資料編]では最近までのデータをアップデートしてあります。

　今回の改訂は，センテニアルに向けた新たな半世紀に大きな一歩を踏み出す契機になるものと自負しております。

　おわりに困難な編集事業に取り組まれた[[ＯＲ事典編集委員会]]の皆様、
ご支援いただいたＯＲ学会５０周年記念事業関係者およびＯＲ学会事務局の方々に心から感謝の意を表します。（2007.9.1）

----

　　　　
　　　　
== 執筆協力者一覧 ==

=== 基礎編、用語編執筆者 ===
:浅野孝夫, 朝野煕彦, 穴太克則, 飯島淳一, 飯田耕司, 石井博昭, 石渡徳彌, 一森哲男, 伊藤和憲, 伊藤健, 乾口雅弘, 茨木俊秀, 今井桂子, 今井浩, 今泉淳, 岩城秀樹, 岩田覚, 岩本誠一, 上田徹, 上野哲郎, 上原隆平, 宇野毅明, 梅沢豊, 大内東, 大隅昇, 太田敏澄, 大西匡光, 大野勝久, 大山達雄, 岡田章, 尾崎俊治, 小沢利久, 小澤正典, 海生直人, 嘉数侑昇, 片岡靖詞, 片桐英樹, 片山隆仁, 片山勁, 片山徹, 刈屋武昭, 川崎英文, 川島幸之助, 川島武, 河野浩之, 城川俊一, 菊田健作, 木瀬洋, 紀一誠, 木村武, 木村俊一, 久野誉人, 久保幹雄, 久保田光一, 栗田治, 倉橋（筑波）, 黒田充, 腰塚武志, 小島政和, 小林和朝, 古林隆, 今野浩, 齋藤雄志, 逆瀬川浩孝, 佐藤馨一, 佐藤大輔, 猿渡康文, 澤木勝茂, 三道弘明, 椎塚久雄, 塩浦昭義, 塩出省吾, 繁野麻衣子, 篠原正明, 下村雅彦, 白川浩, 杉原厚吉, 杉原左右一, 杉山学, 鈴木敦夫, 鈴木和幸, 鈴木賢一, 鈴木久敏, 関口恭毅, 関谷和之, 戴陽, 高井英造, 高木英明, 高橋勝, 高橋真吾, 高橋磐郎, 高橋幸雄, 高橋豊, 高橋敬隆, 滝根哲哉, 田口東, 田中環, 田中雅博, 田中雅康, 谷野哲三, 田畑吉雄, 田村明久, 田村隆善, 田村坦之, 佃純誠, 佃良彦, 土谷隆, 角田康夫, 寺野隆雄, 徳山博干, 刀根薫, 土肥正, 中井暉久, 中川覃夫, 中里宗敬, 中島恭一, 中島康之, 中塚利直, 中西昌武, 中野文平, 中丸麻由子, 永持仁, 長山いづみ, 中山幹夫, 生田目崇, 並木誠, 難波和明, 西岡靖之, 西村彰一, 根本俊男, 野々部宏司, 野村淳二, 橋田温, 蜂谷豊彦, 浜田和樹, 枇々木規雄, 平野雅章, 平林, 福川忠昭, 福島雅夫, 福本聡, 藤井進, 藤江, 藤重悟, 伏見正則, 藤本衡, 船木由喜彦, 古川浩一, 宝崎隆祐, 星野朝子, 堀内正博, 牧本直樹, 増山繁, 町原文明, 松井知己, 松井泰子, 真鍋龍太郎, 丸田利昌, 丸山明, 水谷昌義, 宮川（筑波）, 宮沢政清, 三好直人, 巳波弘佳, 六十里繁, 武藤滋夫, 棟近雅彦, 村松正和, 室田一雄, 毛利進太郎, 森清堯, 守口剛, 森平爽一郎, 森戸晋, 森村英典, 柳浦睦憲, 矢島安敏, 矢部博, 山川栄樹, 八巻直一, 山口俊和, 山口浩, 山下信雄, 山下英明, 山田茂, 山田善靖, 山地憲治, 大和毅彦, 由良憲二, 吉川武男, 吉瀬章子, 和光純, 渡辺隆裕

=== 事例編分類作業担当者 ===
:飯田哲夫, 小澤正典, 後藤順哉, 鈴木秀男, 武田朗子, 田中健一, 中田和秀, 福田恵美子, 宮代隆平, 宮本裕一郎, 森雅夫, 矢島安敏

=== 資料編執筆者 ===
:青木兼一, 朝尾正, 石井博昭, 石田甫, 梅根定, 亀澤善一郎, 児玉正憲, 後藤義雄, 権藤元, 田口東, 時永祥三, 中川覃夫, 永次廣, 西田俊夫, 日比野康文, 藤野義一, 三上操, 三根久, 本告光男, 柳井浩, 横山清, 若林信夫, 若山邦紘

2008-03-13T14:25:55Z

Imahori: 基礎編と用語編のマージ

'''【ばけっとほう (bucket method)】'''

=== 概要 ===
幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.

=== 詳説 ===
　計算幾何の実用的なアルゴリズムの代表的設計法の一つであり, 平面最小重み完全[[マッチング]] (matching), [[点位置決定]] (point location) などが[[バケット法]] (bucket method) に基づいて効率的に解かれている. 簡単のため2次元で説明するが, 高次元にも容易に一般化できる. 平面上にサイズ<math>n\, </math>の解きたい問題が与えられたとする. 問題を含む領域を軸に平行な辺からなる長方形で覆い, 軸に垂直な直線を引いて<math>\Theta(n)\, </math>個のバケットと呼ばれる合同な小長方形に分割する. そして全体の問題をそれぞれのバケット内の問題として分割して記憶する. すると通常はバケット内での問題だけで全体の解が得られるので高速になる. バケット間にまたがる情報を必要に応じて利用しなければならない場合もあるがこの場合も高速な手法があることが多い.

　具体例でより詳しく説明する. 与えられた平面上の<math>n=2m\, </math>個の点集合に対して, <math>2\, </math>点ずつペアにして<math>m\, \, </math>個のペアの集合<math>M\, </math>をつくるという問題を考える. このような<math>M\, </math>は, 完全マッチングと呼ばれている. その際, ペアの重みをそのペアに含まれる<math>2\, </math>点間の距離(<math>2\, </math>点を結ぶ線分の長さ)とする. 完全マッチング<math>M\, </math>の重みを<math>M\, </math>に含まれる<math>m\, </math>個のペアの重みの総和と見なし, 重みを最小にする完全マッチングを求める問題を平面最小重み完全マッチングというが, この問題をバケット法に基づいて解決しその実用性を実証した研究 [2] が, 計算幾何学の問題に対するバケット法の最初の適用例といわれている. できるだけ小さい重みの完全マッチングをつくるわけであるので, 遠く離れた<math>2\, </math>点がペアになる可能性は低い. そこで, 対象領域(長方形領域)を縦横<math>\lceil \sqrt{n}\ \rceil\, </math>等分し全部で<math>\lceil \sqrt{n} \ \rceil \times \lceil \sqrt{n} \ \rceil=\Theta(n)\, </math>個のバケットに分割して, 同一のバケットに含まれる点でまずペアをつくる. 最小重みの完全マッチングには距離の小さい<math>2\, </math>点がペアとして含まれることが多いので, 同一のバケットに含まれるもの同士をペアにするということは, 同一のバケットに含まれる2点は極めて近い点である可能性が高く, 異なるバケットに属する2点は遠くにある可能性が高いという, 自然な仮定に基づいている.

　このように, バケット法では問題を局所領域に限定できるという特徴がある. さらに, 与えられる点の集合が対象領域において一様に分布するときは, <math>n=2m\, </math>個の点に対してほぼ同数個のバケットに分割しているので, 各バケットは平均的に一定数(<math>\mbox{O}(1)\, </math>)個の点しか含まないといえる. したがって, 各バケット内での最小重み完全マッチングは<math>\mbox{O}(1)\, </math>の手間で見つけることができる. このように, バケット法では, バケット内の問題が極めて単純であるという特徴も併せもっている. さらに, バケットは合同な長方形であるため, バケットに含まれる点も簡単に求められるという特徴もある. このような特徴から, バケット法に基づく手法は, 一般に極めて高速となる [1].

　上の平面最小重み完全マッチングの問題では, バケット内での完全マッチングだけでは, 全体の完全マッチングとはならずに, ペアにされていない点が残るのが普通で, 最終的には, バケット間にまたがる点同士でさらにペアをつくっていかなければならないが, これは, <math>2\, </math>次元バケット間の距離を, ある程度忠実に保存するようにして, 一列に並べ, その順番で次々とペアにしていけばよい. このようにして求められた完全マッチングは, 最小重みの完全マッチングでないことが多いが, 詳細な解析により, かなり精度の高い解となることが保証されている [2]. 最適解はネットワークのアルゴリズムを用いて<math>\mbox{O}(n^3)\, </math>の手間で解けるが, 上記のバケット法に基づく方法は<math>\mbox{O}(n)\, </math>の手間であり, 実際の応用では極めて有効である.

　平面最小重み完全マッチングをプロッターでペンを用いて地図を描く際の筆順最適化 (optimal drawing (of map) ) に応用する. 地図をきれいに描くため, 同じ線を<math>2\, </math>度描くことはしないものとする. ペンをおろして線を描いているときもあるし, ペンを上げて次に描くべき線の始まりまで移動しているときもある. 地図を描くという観点からすると, ペンをおろして線を描くという動作は必要不可欠なものである. これに対して, ペンを上げて次に描くべき線の始まりまで移動する動作は, 空送りと呼ばれ無駄な動作であるので, できるだけ少なくするのがよい. さて, 地図が一筆書き可能なら空送りをすることなく描けることになる. 地図が一筆書き不可能ならば空送りの部分に対応する線を付け加えた図で一筆書きできるように変形して描くことになる. プロッターでの描画に要する時間は, ほぼ, この<math>2\, </math>つの動作に要する時間の総和になるので, 描画時間を減らすには, 空送り全体に要する時間を減らせばよい. これらの動作に要する時間は移動量に比例するものとすれば, 空送り全体の移動量(移動距離)を最小にすれば, 描画に要する時間は最小ということになる. これは平面最小重み完全マッチングに帰着できる. 地図が一筆書き不可能ならば奇数本の線が接続する点を全部拾ってきて(すると点は偶数個になる), <math>2\, </math>個ずつペアにして完全マッチングを求め, 完全マッチングに含まれる線を空送りに対応させて付け加えれば一筆書きできることになる. 完全マッチングの選び方により付け加えた線の総長は異なるので, 総長最小の完全マッチングを求める問題となる.

　その他の計算幾何の様々な探索問題に対するバケット法の応用については文献 [1, 3] を参照のこと.

----
'''参考文献'''

[1] T. Asano, M. Edahiro, H. Imai, M. Iri and K. Murota, "Practical Use of Bucketing Techniques in Computational Geometry," in ''Computational Geometry'', G.T. Toussaint, ed., North-Holland, 1985.

[2] M. Iri, K. Murota and S. Matsui, "Heurisitics for Planar Minimum Weight Perfect Matchings," ''Networks'', '''13''' (1983), 67-92.

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

[[Category:計算幾何|ばけっとほう]]

幾何グラフ

2008-03-13T14:24:30Z

Imahori: 基礎編と用語編のマージ

'''【きかぐらふ (geometric graph)】'''

=== 概要 ===
平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.

=== 詳説 ===
　頂点と辺の間の接続関係を指定することによって定義される抽象的なグラフに対して, 頂点と辺を実際に平面に描いて表したグラフを[[幾何グラフ]] (geometric graph) という. 特に, 平面グラフを辺が互いに端点以外では交差しないように描いた幾何グラフが重要である.

　<math>S=\{ {\rm P}_1, {\rm P}_2, \cdots , {\rm P}_n\}\, </math> を平面上に指定された有限個の点の集合とする. 簡単のために, 以下では <math>S\, </math> に属すどの 4 点も同一円周上にはないものと仮定する. <math>S\, </math> に属す 2 点を通り他の点を内部に含まない円が存在するときその 2 点を辺で結ぶことによって, 一つの幾何グラフが得られる. この幾何グラフは <math>S\, </math> に対する[[ドロネー図]] (Delaunay diagram) とよばれる. ドロネー図は <math>S\, </math> の[[凸包]] (convex hull) の内部を三角形に分割した図形となる. この三角形分割はできるだけふっくらとした三角形を使った分割となっているため, 有限要素法などのためのメッシュとしても使われている.

　ドロネー図の辺は, 互いに近い点同士をつないだものとみなすことができる. したがって, ドロネー図は不規則に配置された点に対して「隣り同士」の関係を定義するものとみなすことができる. 実際, 次に示すように, 近さに基づいて定義されたいくつかのグラフはドロネー図の部分グラフとなっている.

　<math>{\rm P}_i, {\rm P}_j \in S\, </math> に対して, <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> の距離を半径とし <math>{\rm P}_i\, </math> を中心とする円と <math>{\rm P}_j\, </math> を中心とする円の共通部分に <math>S\, </math> の他の要素が含まれないとき <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> を線分で結ぶことによってできる幾何グラフは, [[ガブリエルグラフ]] (Gabriel graph) とよばれる. ガブリエルグラフはドロネー図の部分グラフである.

　<math>{\rm P}_i, {\rm P}_j \in S\, </math> に対して, <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> の距離を半径とし <math>{\rm P}_i\, </math> を中心とする円と <math>{\rm P}_j\, </math> を中心とする円のどちらにも<math>S\, </math> に属す他の点が含まれないとき <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> を線分で結ぶことによってできる幾何グラフは[[相対近傍グラフ]] (relative neighborhood graph)とよばれる. 相対近傍グラフはガブリエルグラフの部分グラフである.

　各 <math>{\rm P}_i \in S\, </math> に対して, <math>{\rm P}_i\, </math> を始点とし, <math>{\rm P}_i\, </math> に最も近い<math>S-\{ {\rm P}_i \}\, </math> の要素を終点とする有向辺を集めてできるグラフは[[最近傍グラフ]] (nearest neighbor graph) とよばれる. 最近傍グラフにおいて有向辺で結ばれている 2点の間に線分をひくことによって得られる幾何グラフは, ガブリエルグラフの部分グラフである.

　<math>S\, </math> の凸包の辺から成る図形も幾何グラフである. この幾何グラフもドロネー図の部分グラフである.

　<math>S\, </math> に属す点を頂点とする木 (連結で無サイクルなグラフ) で, 辺の長さの和が最小のものを, [[最小全域木]](minimum spanning tree)という. 最小全域木もドロネー図の部分グラフである.
　<math>S\, </math> に対するドロネー図は <math>{\rm O}(n\log n)\, </math> の計算量で求めることができる. したがって上に述べた幾何グラフは, まずドロネー図を計算し, その辺のみを候補として辺を探すことにより効率よく構成することができる.

　新たに頂点を設けてもよいという条件のもとで <math>S\, </math> に属すすべての頂点をつなぐ辺長の和が最小の木を[[シュタイナー木]] (Steiner tree) という. シュタイナー木の効率のよい構成法は知られていない.

　<math>S\, </math> に属す点の対でその距離が最小のものを[[最近点対]] (nearest pair) という. 最近点対はドロネー図の辺である.

　<math>S\, </math> に属す点の対でその距離が最大のものを[[最遠点対]] (farthest pair)という. 最遠点対は <math>S\, </math> の凸包の頂点のいずれかの対によって実現される.

　平面上に描かれた多角形 <math>T\, </math> に, <math>T\, </math> の内部のみを通過するすべての対角線を加えた幾何グラフを <math>T\, </math> の[[可視グラフ]] (visibility graph)という. このグラフでは一般に辺が交差するため, 平面グラフとは限らない. <math>T\, </math> のある頂点からもう一つの頂点へ移動する <math>T\, </math> 内の最短経路は, 可視グラフの中で最短経路を探すことによって得られる.

　多角形 <math>T\, </math> 内のすべての点を見渡すことのできる, できるだけ少数の監視点を<math>T\, </math> 内に配置する問題は, [[美術館監視問題]] (art gallery problem)とよばれる. この問題の解法にも可視グラフが役立つ.

[[Category:計算幾何|きかぐらふ]]