| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-12-03 15:10 A 4-competitive strategy for exploring unknown polygons ○Xuehou Tan（Tokai Univ.）  COMP2008-52 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | We present a new, on-line strategy for a mobile robot to explore an unknown simple polygon with $n$ vertices, starting at a boundary point $s$, which outputs a so-called {\it watchman route} such that every interior point of $P$ is visible from at least one point along the route. The length of the robot's route is guaranteed to be at most 4 times that of the shortest watchman route that could be computed off-line. This gives a significant improvement upon the previously known 26.5-competitive strategy, and also confirms a conjecture due to Hoffmann et al \cite{Hoffmann2}. A novelty of our competitive strategy is a recursive procedure that reduces the polygon exploration problem to the subproblems of exploring two different types of reflex vertices, which are classified by their turning directions in the shortest path tree of $s$. The other is a mixture of techniques, including the off-line approximation algorithm for the watchman route problem \cite {Tan04}, a geometric structure called the {\it angle hull} \cite{Hoffmann2}, and the paradiam for making the off-line techniques be on-line. |
|
| キーワード | （和） | / / / / / / / |
| （英） | computational geometry / competitive strategy / watchman route problem / polygon exploration problem / angle hull / / / | |
| 文献情報 | 信学技報, vol. 108, no. 330, COMP2008-52, pp. 41-48, 2008年12月. | |
| 資料番号 | COMP2008-52 | |
| 発行日 | 2008-11-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-52 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-12-03 - 2008-12-03 |
| 開催地（和） | 群馬大学 |
| 開催地（英） | Gunma Univ. |
| テーマ（和） | 情報処理学会アルゴリズム研究会との共催 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-12-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | A 4-competitive strategy for exploring unknown polygons |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / computational geometry |
| キーワード(2)（和/英） | / competitive strategy |
| キーワード(3)（和/英） | / watchman route problem |
| キーワード(4)（和/英） | / polygon exploration problem |
| キーワード(5)（和/英） | / angle hull |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 譚 学厚 / Xuehou Tan / タン ガクコウ |
| 第1著者 所属（和/英） | 東海大学 (略称： 東海大) Tokai Univeristy (略称： Tokai Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-12-03 15:10:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-52 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.330 |
| ページ範囲 | pp.41-48 |
| ページ数 | 8 |
| 発行日 | 2008-11-26 (COMP) |
[研究会発表申込システムのトップページに戻る]