複数探索者による単純直交多角形のオンライン探索問題

• Item type: SIG Technical Reports(1)
• 公開日: 2024-05-01
• タイトル: 複数探索者による単純直交多角形のオンライン探索問題
• タイトル / 言語: en
• タイトル: Online Exploration of Rectilinear Polygons by Multiple Searchers
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 兵庫県立大学
• 著者所属: 兵庫県立大学
• 著者所属: 兵庫県立大学
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者名: 阿部, 太郎; 東川, 雄哉; 宮崎, 修一
• 著者名(英): Taro, Abe; Yuya, Higashikawa; Shuichi, Miyazaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，複数探索者による未知な単純直交多角形内の効率的な探索について論じる．探索者は多角形内部の一点から探索を開始し，任意の地点において情報を読み書きすることで他の探索者と情報を共有しながら，多角形内部の全域を視認した後に探索開始地点に戻る．問題の目的は探索終了までの時間を最小化することである．本研究では，ある長方形に対して再帰的に長方形を接続したような特定のクラスの単純直交多角形において，探索者数 ???? に対して競合比 ????(????/log ????) を達成するオンラインアルゴリズムを構築した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider efficient exploration of unknown simple rectilinear polygons by multiple searchers. Searchers start the exploration from a given point in the polygon, and come back to the origin after seeing any point inside the polygon. During the exploration, searchers can communicate each other by writing and reading the information at any point in the polygon. The objective of the problem is to minimize the time needed to finish the exploration. In this study, we present an ????(????/log ????)-competitive online exploration algorithm by ???? searchers for a restricted class of simple rectilinear polygons.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-198, 号 10, p. 1-6, 発行日 2024-05-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会