A study on the algorithms for searching a static or moving target in a polygonal region

我们提出了一种新的在线策略，让移动机器人从边界点开始探索未知的多边形P，它输出一个所谓的守望者静音，使得P的每个内点至少从路线上的一个点都是可见的。机器人的路线长度被保证至少是最短的看守人路线的6.7倍，而最短的路线可以离线计算。对于多边形搜索问题，我们还开发了一种高效的算法。给定一个具有两个顶点u和v的简单多边形P，三重守卫问题是问三个守卫是否可以从u移动到v，使得第一个和第三个守卫分别位于P的两个从u到v的边界链上，并且第二个守卫总是可以被P内的另外两个守卫看到。我们可以确定三个守卫问题是否存在解，如果存在，则在O(Nlogn)时间内生成一条O(Nlogn In)时间内的游动，其中n表示P的顶点数，m(≦(n^2))是最优游动的大小。这分别改进了以前的时间界限O(n^2)和O(n^2logn)。

We presented a new, on-line strategy for a mobile robot to explore an unknown polygon P. starting at a boundary point, which outputs a so-called watchman mute 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 guranteed to be at roost 6.7 times that of the shortest watchman route that cnuld be computed off-line. This gives a significant improvement-upon the previously known 26.5-competitive strategy.For the polygon search problem, we also developed an efficient algorithm. Given a simple polygon P with two vertices u and v, the three-guard problem asks whether three guards can move from u to v such that the first and third guards are separately on two boundary chains of P from u to v, and the second guard is always kept to be visible from two other guards inside P. We can decide whether there exists a solution fir the three-guard problem in O(n log n) time, and ifso, generate a walk in O(n log n+in) time, where n denotes the number of vertices of P and m(≦(n^2)) the size of the optimal walk. This improves upon the previous time bounds O(n^2) and O(n^2 log n), respectively.