チェーンガイドによる多角形の捜索アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2006-01-20
• タイトル: チェーンガイドによる多角形の捜索アルゴリズム
• タイトル / 言語: en
• タイトル: Sweeping simple polygons with the mimimum number of chain guards
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東海大学 開発工学部
• 著者所属(英): en
• 著者所属(英): School of High-Technology for Human Welfare Tokai University
• 著者名: 譚, 学厚
• 著者名(英): Xuehou, TAN
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論では、k+1人の捜索員が一つのチェーンになって単純多角形における移動対象を捜索する問題について調べる。まず、「リンクーk図」と呼ばれるデータ構造を提案する。リンクーk図では、リンク距離がkを超えない点対はすべて記録され、また最短リンクパスにおける推移関係も記録されている。次に、単純多角形における動的対象を捜索するのに必要な最小の捜索員の数r*をO(n2)時間で計算するアルゴリズムを提案する。捜索できる場合には、捜索のスケジュールをO(r*n2)時間で報告する。我々の結果は今までのアルゴリズムを線形時間も改善した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the problem of detecting a moving target using a group of k+1 (k is a positive integer) mobile guards inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that consecutive guards along the chain are mutually visible. In this paper, we introduce the notion of the link-k diagram of a polygon, which records all the pairs of points on the polygon boundary such that the link distance between any of these pairs is at most k and a transition relation among minimum-link (＜ k) paths as well. An O(n2) time algorithm is then presented to compute the minimum number r* of guards required to detect the target, no matter how fast the target moves. Moreover, a sweep schedule can be reported in O(r*n2) time. Our results improve upon the previously known time bounds by a linear factor.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 7(2006-AL-104), p. 17-24, 発行日 2006-01-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会