Firefighting! Strategies for Random Geometric Graphs using an Analytic Approach

Abstract

In this bachelor thesis, we investigate some strategies for the firefighting problem on the random geometric graph. The firefighting problem is a problem on graphs where fire breaks out on a set of vertices. Each subsequent turn we can protect vertices using firefighters, after which the fire spreads to all unprotected neighbours of vertices on fire. The process ends when the fire cannot spread anymore. The protected vertices and the vertices not on fire are the vertices saved. A random geometric graph is a graph of which the vertices are obtained by a homogeneous Poisson Point Process of intensity λ. Vertices are connected by edges if they are distance at most 1 apart. We explain the proof from [3] that we can bound the number of firefighters needed to contain the fire from above by 2λ. We do so by translating the firefighting problem to the problem of surrounding a continuously growing blob with a fence built at rate ρ. We explain the proof from [3] that the blob can be surrounded by a teardrop-shaped fence built at rate ρ > 2 and that the blob cannot be surrounded by a fence built at rate ρ ≤ 1. Finally, we consider a blob with wind. In the real world fire propagation is influenced by wind. We therefore assume that the blob grows faster in the direction of the wind, we call this region the fire front and slower in opposite direction, obtaining a blob with wind. We find that for a blob with wind with an ellipse-shaped fire front with maximum propagation speed vmax, we can surround the blob with a teardrop-shaped fence built at rate ρ > 2.