Capture bounds for visibility-based pursuit evasion

摘要

We investigate the following problem in the visibility-based discrete-time model of pursuit evasion in the plane: how many pursuers are needed to capture an evader in a polygonal environment with obstacles under the minimalist assumption that pursuers and the evader have the same maximum speed? When the environment is a simply-connected (hole-free) polygon of n vertices, we show that Theta(n(1/2)) pursuers are both necessary and sufficient in the worst-case. When the environment is a polygon with holes, we prove a lower bound of Omega(n(2/3)) and an upper bound of O (n(5/6)) for the number of pursuers that are needed in the worst-case, where n is the total number of vertices including the hole boundaries. More precisely, if the polygon contains h holes, our upper bound is O (n(1/2)h(1/4)) for h <= n(2/3), and O (n(1/3)h(1/2)) otherwise. We then show that with additional assumptions these bounds can be drastically improved. Namely, if the players' movement speed is small compared to the "feature size" of the environment, we give a deterministic algorithm with a worst-case upper bound of O (logn) pursuers for simply-connected n-gons and O (root h + logn) for multiply-connected polygons with h holes. Further, if the pursuers are allowed to randomize their strategy, regardless of the players' movement speed, we show that O (1) pursuers can capture the evader in a simply connected n-gon and O (root h) when there are h holes with high probability. (C) 2014 Elsevier B.V. All rights reserved.