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（n log n）时间内决定三守卫问题是否存在解，如果是，在O（n log n+in）时间内生成一个遍历，其中n表示P的顶点数，m（n（n^2））是最优遍历的大小。时间复杂度为O（n^2），时间复杂度为O（n^2 log n）

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.