The Polygon Exploration Problem
The Polygon Exploration Problem
复制标题
DOI：
10.1137/s0097539799348670
复制
发表时间：
2002-02
期刊：
影响因子：
--
通讯作者：
Frank Hoffmann;Christian Icking;R. Klein;K. Kriegel
中科院分区：
文献类型：
--
作者：
Frank Hoffmann;Christian Icking;R. Klein;K. Kriegel
我们提出了一种在线策略，使具有视觉的移动机器人能够探索未知的简单多边形。我们证明了所得到的巡视长度不到离线计算的最短值班巡视的26.5倍。我们的分析双重建立在一种称为角壳的新几何结构上。设D是一个简单多边形P内的连通区域，我们定义D的角壳${cal AH}(D)$是P中可以看到D的两点成直角的所有点的集合。我们证明了$\cal AH}(D)$的周长不能超过D的周长的2倍，这个上界是紧的。
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.