可視グラフ

提供: ORWiki
2007年7月11日 (水) 21:46時点における124.144.188.143 (トーク)による版
ナビゲーションに移動 検索に移動

【かしぐらふ (visibility graph)】

多角形 が与えられたとき, の内部のみを通過する線分で結べる頂点対をすべて結んでできるグラフを の可視グラフという. 多角形の辺を不透明な壁とみなしたとき, 互いに見える頂点同士をつないだものと解釈できる. 建物内に監視カメラを配置する問題などで使われる.