ストレートウォーカーブル多角形におけるエッジガードについて
スポンサーリンク
概要
- 論文の詳細を見る
本研究ではストレートウォーカーブル多角形におけるエッジガード問題を調べる。この問題は美術館問題の一つの変種である。エッジガードは多角形の辺をパトロールできるガードである。単純多角形Pに頂点sとgが与えられるときに、sとgはPの境界線を二つの輪に分ける。二人のガードが二つの輪に沿ってsからgまで互い見えるようにパトロールすることを考える。パトロールの途中後戻りしないでsからgに到達することができれば、Pをストレートウォーカーブル多角形と言う。例えば、単調多角形と螺旋多角形はストレートウォーカーブル多角形である。本研究ではn頂点のストレートウォーカーブル多角形に対し⌊(n+2)/5⌋エッジガードが必要十分であるを証明する。さらに、直交ストレートウォーカーブル多角形に対し⌊(n+3)/6⌋エッジガードが必要十分であることも示す。
- 一般社団法人情報処理学会の論文
- 1995-07-20
著者
関連論文
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : カメラコントロールによる広域コラボレーションの実現法(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : 管腔臓器の領域抽出からドローネ三角形分割によるモデリングまで(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web3Dによる画像診断支援システムの開発-その2
- Web3Dによる画像診断支援システムの開発-その1
- Web3Dによる画像診断支援システムの開発(その1) (第31回可視化情報シンポジウム講演論文集) -- (一般講演 可視化の応用 2)
- 警備員巡回路問題と動物園巡回路問題に対する近似アルゴリズム
- 警備員経路アルゴリズムの時間解析について
- チェーンガイドによる多角形の捜索アルゴリズム(セッション1)
- Κ-探索者による単純多角形の探索問題について
- ストレートウォーカーブル多角形におけるエッジガードについて
- 動物園経路問題に関する新しいアルゴリズム