視角90度の監視員の直多角形ギャラリへの配置アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
n個の辺で構成された多角形の内部を点光源でくまなく照射, あるいは監視員によって監視する際, 何個の光源あるいは何人の監視員が必要かを問う問題は, 一般にアートギャラリ監視問題とよばれている.ギャラリを構成する多角形が一般の多角形の場合には, ⌊n/3⌋人の監視員(点光源)が必要でありかつ十分であることが証明されている.また, 多角形が互いに直交する辺で構成される, いわゆるn辺直多角形である場合には, ⌊n/4⌋人の監視員が必要かつ十分であること, 視野角が90度に限定された監視員をギャラリの辺(壁)に配置するという制限をつけても, ⌊n/4⌋の監視員でギャラリ全体を監視することができることも証明されている.しかし, その証明法では明らかな配置手順が示されていないので, 本論文では, できる限り少ない人数の監視員を配置することも考慮し, 壁に⌊n/4⌋人以下の監視員を具体的に配置するアルゴリズムを与えた.
社団法人電子情報通信学会の論文
1998-08-25

著者

関連論文

もっと見る

スポンサーリンク