A graph-based approach to the visibility-based pursuit-evasion problem

本文提出了一种新的基于可行性的追逃问题的求解方法，主要是将追逃问题转化为图中的最短路问题。对于两个守卫问题，我们给出了O（n^2）时间算法来计算搜索时间表，其中两个守卫移动的距离之和最小化，或者两个守卫之间的最大距离最小化。对于两个1-搜索器搜索圆形走廊中的移动的入侵者的问题，给出了O（n*n）时间的解.对于从给定的n个点中寻找一条在点处转弯但避开给定的m个顶点的多边形边界的简单路径的问题，我们给出了一个O（（n*n+m）log m）时间的算法，大大改进了以前的O（（n m）*（n m））时间限制.最后，我们还给出了LR可见多边形的一个简单刻画和判定给定多边形是否LR可见的线性时间算法。

This work presents a new method for solving the visibility-based pursuit-evasion problems, mainly by transforming them into the shortest path problems in graphs. For the two-guards problem, we presented the O(n^2) time algorithms for computing the search schedules in which the sum of the distances traveled by the two guards is minimized, or the maximum distance between the two guards is minimized. For the problem of searching mobile intruders in a circular corridor by two 1-searchers, we gave an O(n*n) time solution. For the problem of finding a simple path that turns at the points from the given n points but avoids the boundary of the given polygon of m vertices, we presented an O((n*n+m) log m) time algorithm, which greatly improves upon the previous O((n m)*(n m)) time bound. Finally, we also gave a simple characterization of LR-visibility polygons and a linear-time algorithm for determining whether a given polygon is LR-visible.