今回のテーマは美術館問題(art gallery problem)。
・問題
多角形の美術館において、何台の監視カメラがあれば
館内全てを監視する事が出来るか？
監視カメラは360度全てを見渡せるものとする
美術館の形に関しては……
多少違いがあるかもしれませんが、
ペイントで作ってみました。
中の黒塗りの部分は柱になっています。
この問題、4台の監視カメラが必要なことはすぐに分かります。
しかし、4台が最低限の台数という証明に
頭を悩ませていました……。
解答を待っていたのですが、とても原始的な方法で
4台必要であると説明していました。
単純だったけど気づかない……
これは数学の問題の証明では良くある事です。
色々な問題で質問を受けますが、
8割以上の問題ですぐに答える事が出来ます。
しかし残りの問題に関しては、忘れているor見た事が無い為、
すぐに答える事ができない場合があります。
そうなると考えを巡らせていくのですが、
基本的には難しい方法で考えてしまいがちで、
原始的な方法を見落としてしまう事が良くあります。
この問題の説明はまさにそんな感じでした。
この問題での証明は理解できましたが、
これまた一般化しようとすると難しいですね。
良くぞ体系化できたですね……しかもかなり簡単。
詳しくは計算幾何学の美術館問題を調べて見てください。
ちょっと毛色の変わった問題でしたが、面白かったです。
PR
