可視グラフ

【かしぐらふ (visibility graph)】

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