Abstract | ||
---|---|---|
We consider searching problems in robotics that a robot has to find a path to a target by traveling in an unknown starshaped polygon P. The goal is to minimize the ratio of the distance traveled by the robot to the length of the shortest start-to-target path. Let s be a starting point in P. We first present a competitive strategy to find a path from s to the closest kernel point k of P. The length of the path that the robot generates is less than 1 + 2W (< 3.829) times the distance from s to k, which improves the best previous bound 5.331 [3]. Second, given a specified target t in P, we present a competitive strategy to find a path from s to t whose length does not exceed 17 times the length of the shortest s-t path. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1145/262839.263062 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
unknown star-shaped polygon,new competitive strategy,visualization,competitive strategy | Polygon,Visualization,Computer science,Geometric computing,Theoretical computer science,End-user computing,Utility computing | Conference |
ISBN | Citations | PageRank |
0-89791-878-9 | 4 | 0.69 |
References | Authors | |
7 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jae-Ha Lee | 1 | 144 | 14.19 |
Chan-su Shin | 2 | 206 | 26.76 |
Jae-Hoon Kim | 3 | 268 | 65.73 |
Sung Yong Shin | 4 | 1904 | 168.33 |
Kyung-Yong Chwa | 5 | 919 | 97.10 |