Κ-探索者による単純多角形の探索問題について

• Item type: SIG Technical Reports(1)
• 公開日: 1999-05-10
• タイトル: Κ-探索者による単純多角形の探索問題について
• タイトル / 言語: en
• タイトル: Searching a Simple Polygon by a κ - Searcher
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東海大学開発工学部
• 著者所属(英): en
• 著者所属(英): Tokai University
• 著者名: 譚, 学厚
• 著者名(英): Xuehou, Tan
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: この論文では、κ個の方向を見ることができるκ?探索者による多角形探索の必要十分条件を与える。それにより、2?探索者と∞?探索者に能力の差がないことが示されている。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The polygon search problem is the problem of searching for a mobile intruder in a simple polygon by the mobile searcher having flashlights whose visibility is limited to the rays emanating from his position. The intruder can move arbitrarily faster than the searcher. A searcher is called the k-searcher if he can see along k rays emanating from his position, and the ∞-searcher if he has a 360^0 field of vision. We present the necessary and sufficient conditions for a polygon to be searchable by a 1-searcher and by a 2-searcher, and give O (n^2) time algorithms for testing the 1-searchability and 2-searchability of simple polygons and O (n^3) time algorithms for generating a search schedule if one exists. We also show that any polygon that is searchable by an ∞-searcher is searchable by a 2-searcher, which confirms a conjecture due to Suzuki and Yamashita.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1999, 号 33(1999-AL-068), p. 41-48, 発行日 1999-05-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会