# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 5 A PTAS for the Budget Fence Problem and a Special Case of the Firefighter Problem  
Recall that an instance of the budget fence problem consists of a simple polygon \(P\) of \(n\) edges, a \"contaminated\" connected region \(R\) contained within \(P\) (it can be degenerated to a point), the available total fence length \(l\), and an allowed set \(B\) of barriers, none of them intersecting the interior of \(R\). The objective is to fence off from \(R\) the largest possible area of polygon \(P\) by barriers from \(B\) of total length not exceeding \(l\). While \(B\) may contain candidates that cross each other, an algorithm may use only barriers whose interiors are pairwise disjoint. In the absence of time constraints, this problem seems of a more combinatorial nature than the firefighter problem. First, let us assume that \(B\) consists of diagonals of \(P\). Then the following standard dynamic programming and discretization approach yields a close approximation. For each pair \(a,\ b\) of vertices of \(P\), and a number parameter \(s\), we consider the problem \(Q(a,b,s)\) of finding a shortest simple path saving at least an area of size \(s\), from \(a\) to \(b\) in clockwise direction; the path can contain diagonals from \(B\) and edges of \(P\) between \(a\) and \(b\), but only the total length of diagonals counts. Let \(max\) be the maximum area that can be saved by a single diagonal. Clearly, no path can save more area than \(max\times n\). We may assume the parameter \(s\) belongs to \(S=\{i\times max\times n/p(n)\ |\ 0\leq i\leq p(n)\wedge i\in Z^{+}\}\), where \(p(n)\) is an appropriate polynomial. Then, we can solve \(Q(a,b,s)\) by considering solutions to all pairs \(Q(a,c,s_{1})\) and \(Q(c,b,s_{2})\), where \(c\) is a vertex between \(a\) and \(b\) in clockwise direction on the perimeter of \(P\), \(s_{1},s_{2}\in S\), and \(s_{1}+s_{2}\geq s\). We pick the pair that minimizes the length of the path from \(a\) to \(b\) through \(c\) and compare it with the direct diagonal connection between \(a\) and \(b\) if this diagonal exists in \(B\). We obtain an approximate solution of the budget fence problem for \(P\) by picking the largest \(s\in S\) such that the minimum length path solving \(Q(a,a,s)\) for some vertex \(a\) of \(P\) has length less than or equal to \(l\). Any feasible solution includes at most \(\lceil n/2\rceil\) diagonals. By the definitions of \(S\) and our dynamic programming scheme, the area saved by each of them can be underestimated by at most \(\frac{n\times max}{p(n)}\). Hence, since the optimal solution saves at least \(max\), the approximation factor of our dynamic programming method is \(\frac{1}{1-n^{2}/p(n)}\). It follows that it is sufficient to set \(p(n)\) to \(cn^{2}\), for a sufficiently large constant \(c\), in order to obtain a \((1+\epsilon)\) approximation. Note that this method can be immediately adapted to work for any finite set \(B\) of straight-line barriers within \(P\setminus R\) with all endpoints on the polygon boundary (extending the set of vertices). Hence, we have the following theorem. There is a PTAS for the budget fence problem for a simple polygon \(P\) and a contaminated region \(R\), where the set \(B\) of allowed barriers is any finite set of straight-line segments within \(P\setminus R\) having all endpoints on the boundary of \(P\) and the selected barriers have pairwise disjoint interiors. Remarkably, a good approximation to the budget fence problem can also yield a good approximation to the firefighter problem, under the assumptions from above (barriers are straight-line segments within \(P\) and all barriers chosen must have pairwise disjoint interiors). In fact, we obtain the following corollary from Theorem 4. Let \(P\) be the input polygon and let the set \(B\) of allowed barriers in \(P\) be a finite set of straight-line segments within \(P\) having all endpoints on the boundary of \(P\). Next, let \(\min_{B}\) and \(\max_{B}\) be, respectively, the minimum and maximum geodesic distance of a barrier in \(B\) from the fire source.