# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 1 Introduction  
The _firefighter problem in graphs_ has recently received significant attention [1; 2; 3; 4]. It models a situation where a fire, infection, computer virus, etc., spreads through a network, and the goal is to save as many network nodes as possible by a suitable placement of firefighters.  
At the beginning a fire breaks out at the source vertex of the input graph. At each subsequent time step a bounded number of firefighters (just one in the standard version) may be placed at vertices that are not already on fire, to defend them. Once defended, a vertex will never catch fire. After the firefighters have been placed, the fire spreads from each burning vertex to all its undefended neighbors. The process ends when the fire can no longer spread. All vertices which are not on fire are considered to be _saved_. The objective is to determine a placement of firefighters that maximizes the number of vertices saved.  
This graph firefighter problem is NP-hard already for trees [3; 5], and hard to approximate within \(n^{\alpha}\), for any \(\alpha<1\), in polynomial-time in the general case [2]. Only trees are known to admit polynomial-time constant-factor (\(e/(e-1)\approx 1.5819\)) approximation algorithms [2].  
Real firefighting takes place in environments different from graphs. The importance of the problem poses a big challenge to research: how should fire brigades best deploy their forces in order to efficiently quench or contain a raging fire?In this paper we focus on geometric aspects of the problem, leaving aside, for now, additional constraints imposed by climate, geology, area utilization and other factors. We propose a natural _geometric firefighter problem_. Instead of a graph, we consider a polygonal region \(P\) with a distinguished point \(R\) where a fire starts spreading through \(P\) at a given constant speed. Instead of placing firefighters, we can build one-dimensional barriers (i.e., straight-line segments or curves) also at a given constant speed in the area still free of fire, one at a time. Thus, building a barrier takes time proportional to its length. A barrier must be built continuously and each barrier point must be completed before the fire reaches any point on the yet not completed fragments of this barrier. The goal is to maximize the area of \(P\) that is separated from the fire by the barriers. All edges of the boundary of \(P\) are assumed to be already constructed or natural barriers. (Our results can be modified to apply to other variants of the problem. For example, the fire can spread at various speeds, and the time it takes to build various barriers can also vary.)  
We also consider a simpler version termed the _budget fence problem_. For a polygonal region \(P\), a contaminated subregion \(R\), and a fence budget \(l\), we want to separate a maximum area of \(P\) from \(R\) by drawing barriers within \(P\setminus R\) of total length not exceeding \(l\). In this static case no time constraints need to be observed.  
Both problems have several variants depending on the type of polygonal region and the set \(B\) of barriers allowed.