The Polygon Exploration Problem: A New Strategy and a New Analysis Technique
Pankaj K. Agarwal, Lydia E. Kavraki, Matthew T. Mason · 1998
We provide a new on-line strategy that enables a mo bile robot with vision to explore an unknown polygon by a tour less than 26.5 times as long as the shortest watchman tour. This improves considerably on the best upper bound of 133 known so far. Our strategy uses a new way of dynamically decomposing the polygon. The analysis is based on a novel geometric structure called the angle hull.