| Presentation | 2008-12-03 A 4-competitive strategy for exploring unknown polygons Xuehou TAN, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 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. 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, a geometric structure called the angle hull, and the paradiam for making the off-line techniques be on-line. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Computational geometry / Competitive strategy / Watchman route problem / Polygon exploration problem / Angle hull |
| Paper # | COMP2008-52 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2008/11/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A 4-competitive strategy for exploring unknown polygons |
| Sub Title (in English) | |
| Keyword(1) | Computational geometry |
| Keyword(2) | Competitive strategy |
| Keyword(3) | Watchman route problem |
| Keyword(4) | Polygon exploration problem |
| Keyword(5) | Angle hull |
| 1st Author's Name | Xuehou TAN |
| 1st Author's Affiliation | Tokai University() |
| Date | 2008-12-03 |
| Paper # | COMP2008-52 |
| Volume (vol) | vol.108 |
| Number (no) | 330 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |