On Discrete and Geometric Firefighting

Abstract

Wildfires ravaging forests around the globe cost lives, homes and billions in damages every year, which motivates the study of effective firefighting. In the area of theoretical computer science, several different models inspired by firefighting have been established and studied to find efficient firefighting strategies.</br>In Hartnell’s fire fighter problem, a fire burns through the vertices in a graph in rounds: in each round, the fire spreads from each burning vertex to all adjacent vertices. A firefighter is tasked with protecting as many vertices of the graph as possible by blocking a single vertex each round. While a plethora of results have been obtained with respect to specific graph classes or variations of the firefighter’s power, the modus operandi of the fire rarely changes.</br>We study a new model generalizing the one used by Hartnell to better simulate the varying speeds, at which a fire spreads through different terrain types, by incorporating a fire resistance and energy for each vertex. We present an efficient algorithm to track the fire propagation in a given graph G = (V,E) in time O(|E| · |V|), that is particularly efficient in graphs with bounded vertex degree, where its runtime lies in O(|V| log |V|). We also obtain polynomial-time algorithms for two problems regarding protecting a set of vertices along the boundary of a hexagonal cell graph. We show NP-completeness for an inverted third problem, where the goal is instead to ignite a set of target cells given a set of starter cells. We also examine the unique features of the model and propose a number of new questions utilizing them.</br>In the second part of this thesis we focus on geometric firefighting as introduced by Bressan. In that model, the fire burns a region of the Euclidean plane that grows over time with unit speed, and has to be contained by building barrier curves with some building speed v. In the original problem, the exact necessary building speed to contain the fire is not known, as a gap remains between the best known strategy for a speed of v > 2 and a lower bound of v > 1. The difficulty in closing this gap seems to lie with the following question: <em>To contain a fire, should one build an enclosing barrier at maximum speed, or is it better to invest some time in building extra delaying barriers that will not be part of the final enclosure but can slow the fire down during construction?</em></br>To get a step closer to the answer to this question, we mainly study a variant of the original problem, where a fire spreading at unit speed according to the L₁-metric is to be contained in an open half-plane. Towards that goal, the firefighter is allowed to build one infinite enclosing barrier along the x-axis, and vertical delaying barriers attached to it. We prove that at least a building speed of v > 1.6 is necessary to contain the fire in this variant, while providing a strategy that suceeds for a speed v > 1.8772. We also study some smaller variants of both this and the original problem.</br>In the final part of this thesis, we study the Minimum Enclosing Ball problem in high dimensions: given a set of n points in the d-dimensional Euclidean space, find the ball of minimum radius containing all points. This is a classic clustering problems and has been studied extensively in the past, often together with its generalization, the Euclidean k-center problem. Among the known results are polynomial-time algorithms to obtain optimal solutions for fixed k and d by Megiddo and Welzl, polynomial-time (1+ε)-approximation algorithms for k = 1, but arbitrary d (see Bădoiu and Clarkson or Kumar et al.) as well as – most recently – a polynomial-time algorithm for instance with rational coefficients by Rösner. However, it can not be solved in polynomial time for general d. We provide a simple gradient-descent based (1+ε)-approximation algorithm, that runs in time O(nd 1/ε ) and improves on the similar core-set based approximation algorithms.