Optimal Algorithms for a Pursuit-Evasion Problem in Grids
Kazuo Sugihara, I. Suzuki · SIAM Journal on Discrete Mathematics · 1989
This paper discusses a problem of searching for and capturing a fugitive by a team of searchers in an $N \times N \,\text{grid}\,G_N $ representing a system of Navenues and Nstreets which a searcher can “see” a fugitive if and only if both are on the same avenue or the same street. A $0.5N^2 + O(N)$ time algorithm is presented for searching $G_N $ by a team of two searchers in order to decide whether there exists a fugitive in $G_N $. The algorithm is shown to be (1) optimal with respect to the number of searchers required for the case in which the fugitive can move at least as fast as the searchers, and (2) asymptotically optimal with respect to the worst case time complexity. An $O(N^2 )$ time algorithm is also presented for capturing a fugitive in $G_N $ by a team of four searchers. The algorithm is shown to be asymptotically optimal with respect to the worst case time complexity.