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

糟谷 咲子  後藤 宗弘  松本 忠博  

誌名
電子情報通信学会論文誌 A   Vol.J81-A   No.8   pp.1175-1180
発行日: 1998/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造計算複雑度
キーワード: 
直多角形,  アートギャラリ問題,  監視員,  視角90゜,  

本文: PDF(378.4KB)>>
論文を購入




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