论文标题
逃脱多边形
Escaping a Polygon
论文作者
论文摘要
假设一个“逃脱”的玩家在区域内部以最大速度1的速度连续移动，而“追求”玩家以最大速度$ r $在区域之外的最大速度持续移动。对于第一个球员可以逃脱该地区的$ r $，即假设两个球员的最佳比赛都与追捕球员的正距离距离边界？我们为这种无限交流的2播放器游戏形式化了一个模型，我们证明，该游戏在任何具有本地可纠正边界的地区都有独特的赢家，避免了以前在某些指标空间中识别出诸如狮子和男人问题之类的追捕效率游戏的病理行为（这两个玩家都可以拥有“赢得策略”）。对于包括等边三角形和广场在内的某些地区，我们为临界速度比例提供了确切的结果，而追求球员可以获胜，而逃脱的球员可以赢得胜利（并且追捕球员可以获胜）。对于简单的多边形，我们提供了一个简单的公式和多项式时间算法，该算法可以保证给临界速度比例提供10.89898-Approximation，并且我们给出了伪繁殖的时间近似方案，以任意近似临界速度比率。在负面方面，我们证明了3D中多面体域的问题的NP硬度，并证明了对多个逃避和追求球员的概括（pspace-hardness and np-hardness to近似）。
Suppose an "escaping" player moves continuously at maximum speed 1 in the interior of a region, while a "pursuing" player moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game that we prove has a unique winner in any region with locally rectifiable boundary, avoiding pathological behaviors (where both players can have "winning strategies") previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for arbitrarily approximating the critical speed ratio. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players.
