How many lions are needed to clear a grid?

DOI10.3390/A2031069MaRDI QIDQ1662492zbMATH OpenOpenAlexFDO

Authors Florian Berger, Alexander Gilbers, Ansgar Grüne, Rolf Klein

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a2031069

zbMATH Keywords

avoidance numbergraph searchgraph separatorisoperimetric inequalitylion and manpursuit gamessafe path planning

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Review text

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.

Recommendations

• Lions and contamination: monotone clearings
• Lions and contamination, triangular grids, and Cheeger constants
• Best laid plans of lions and men
• Escaping an infinitude of lions
• \(k\)-capture in multiagent pursuit evasion, or the lion and the hyenas

Cites work

• A Separator Theorem for Planar Graphs
• Compressions and isoperimetric inequalities
• Escaping offline searchers and isoperimetric theorems
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 3080510 (Why is no real title available?)
• Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning
• Recontamination does not help to search a graph
• The On-Line Encyclopedia of Integer Sequences
• Vertex-to-vertex pursuit in a graph
• “Lion and Man”: Upper and Lower Bounds

Cited in

(10)

• Reversibility properties of the fire-fighting problem in graphs
• Lions and contamination, triangular grids, and Cheeger constants
• Searching for an intruder on graphs and their subdivisions
• Lions and contamination: monotone clearings
• On a fire fighter's problem
• Geometric firefighting in the half-plane
• Improved bounds for cops-and-robber pursuit
• Non-adaptive and adaptive two-sided search with fast objects
• An isoperimetric inequality and pursuit-evasion games on triangular grid graphs
• A local strategy for cleaning expanding cellular domains by simple robots

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: How many lions are needed to clear a grid?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662492)