Escaping a Polygon
Zachary Abel, Hugo Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jason S. Ku, Jayson Lynch
假设一个逃跑的玩家(“人类”)在一个区域内部以最高速度1连续移动,而追求的玩家(“僵尸”)以区域外的最大速度r连续移动。 对于什么r可以逃离该地区,即到达边界一个积极的距离追求的玩家,假设双方的最佳发挥? 我们正式确定了这个无限交替的2人游戏的模型,并证明它在任何本地可纠正的区域都有一个独特的赢家。 因此,我们的模型避免了病态行为(玩家都可以有“获胜策略”),这些游戏以前在某些度量空间中为追逐逃避游戏(如狮子和人的问题)确定。 对于某些特定区域,包括等边三角形和正方形,我们给出了关键速度比的确切结果,上面追求的玩家可以赢,并且低于逃跑的玩家可以获胜(以及追求玩家可以获胜)。 对于简单的多边形,我们给出一个简单的公式和多项式时间算法,保证给10.89898-近似临界速度比,我们给出一个伪多项式时间近似方案,用于任意紧密地近似临界速度比。 在消极方面,我们证明了3D中多面体域问题的NP硬度,并证明了对多个逃逸和追求玩家的概括(PSPACE-hardness和NP-hardness甚至近似)的更强结果。
Suppose an escaping player ("human") moves continuously at maximum speed 1 in the interior of a region, while a pursuing player ("zombie") 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 and prove that it has a unique winner in any locally rectifiab...