動物園経路問題に関する新しいアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
Pを単純多角形とし、P'をPの境界線に付けられる凸多角形の集合とする。動物園経路問題とは、P'の多角形をすべて訪れる最短経路を求めることである。nを多角形PとP'の各多角形の総辺数とする。本論文では動物園経路問題を解く二つの新しいアルゴリズムを与える。一つは決定的なアルゴリズムであり、O(kn)の時間を要する。ここでkはP'の多角形の最大サイズである。もう一つは線形時間で近似解法を与える。近似解は最適解のπ/2倍内であることが保証される。これらのアルゴリズムは以前の結果を改良する。
- 一般社団法人情報処理学会の論文
- 1995-01-23
著者
関連論文
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : カメラコントロールによる広域コラボレーションの実現法(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : 管腔臓器の領域抽出からドローネ三角形分割によるモデリングまで(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web3Dによる画像診断支援システムの開発-その2
- Web3Dによる画像診断支援システムの開発-その1
- Web3Dによる画像診断支援システムの開発(その1) (第31回可視化情報シンポジウム講演論文集) -- (一般講演 可視化の応用 2)
- 警備員巡回路問題と動物園巡回路問題に対する近似アルゴリズム
- 警備員経路アルゴリズムの時間解析について
- チェーンガイドによる多角形の捜索アルゴリズム(セッション1)
- Κ-探索者による単純多角形の探索問題について
- ストレートウォーカーブル多角形におけるエッジガードについて
- 動物園経路問題に関する新しいアルゴリズム