How many lions are needed to clear a grid? (Q1662492): Difference between revisions

Summary: We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. \textit{P. Brass} et al. [Comput. Geom. 42, No. 2, 119--126 (2009; Zbl 1156.68574)] showed that \(\frac{n}{2}\) lions are not enough to clear the \(n\times n\)-grid. In this paper, we consider the same problem in dimension \(d>2\) and prove that \(\Theta(n^{d-1}/\sqrt d)\) lions are necessary and sufficient to clear the \(n^d\)-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.