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.