| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2008-12-03 15:10 A 4-competitive strategy for exploring unknown polygons Xuehou Tan (Tokai Univ.)  COMP2008-52 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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 {\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. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | computational geometry / competitive strategy / watchman route problem / polygon exploration problem / angle hull / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 108, no. 330, COMP2008-52, pp. 41-48, Dec. 2008. | |
| Paper # | COMP2008-52 | |
| Date of Issue | 2008-11-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2008-52 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2008-12-03 - 2008-12-03 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Gunma Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2008-12-COMP |
| Language | English |
| 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 |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Xuehou Tan |
| 1st Author's Affiliation | Tokai Univeristy (Tokai Univ.) |
| 2nd Author's Name | |
| 2nd Author's Affiliation | () |
| 3rd Author's Name | |
| 3rd Author's Affiliation | () |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2008-12-03 15:10:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2008-52 |
| Volume (vol) | vol.108 |
| Number (no) | no.330 |
| Page | pp.41-48 |
| #Pages | 8 |
| Date of Issue | 2008-11-26 (COMP) |
[Return to Top Page]