Name
Abstract | ||
|---|---|---|
We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line.Our analysis is doubly founded on a novel geometric structure called angle hull. Let D be a connected region inside a simple polygon, P. We define the angle hull of D, ${\cal AH}(D)$, to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of ${\cal AH}(D)$ cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S0097539799348670 | SIAM J. Comput. |
Keywords | Field | DocType |
computational geometry,curve length,unknown simple polygon,on-line algorithm,cal ah,resulting tour,robot.,competitive strategy,angle hull,connected region,simple polygon,polygon,motion planning,right angle,polygon exploration problem,optimum watchman tour,mobile robot,novel geometric structure,navigation,shortest watchman tour,upper bound,robot | Discrete mathematics,Combinatorics,Right angle,Polygon,Vertex angle,Polygon covering,Upper and lower bounds,Perimeter,Pick's theorem,Simple polygon,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 2 | 0097-5397 |
Citations | PageRank | References |
47 | 2.08 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Hoffmann | 1 | 575 | 51.49 |
| Christian Icking | 2 | 364 | 33.17 |
| Rolf Klein | 3 | 237 | 19.69 |
| Klaus Kriegel | 4 | 242 | 26.37 |