Solving the Art Gallery Problem in Iterations

Abstract

The Art Gallery problem is a famous problem in the field of Computational Geometry. The variant of the problem discussed in this thesis is defined as follows: given a polygon (possibly with holes) $P$, the goal is to find the smallest set of point guards $G \subset P$ such that every point $p \in P$ is at least seen by one of the guards $g \in~G$. A guard $g$ sees a point $p \in P$ if the segment $pg$ is contained in~$P$.

We discuss the practical implementation of \viterative that is used to solve this famous visibility problem. This algorithm has theoretical guarantees, as shown by Hengeveld and Miltzow, in a paper written during this thesis. Aside from the vision-stable iterative algorithm, two of its subroutines were implemented as well. One of these algorithms is used to compute weak visibility polygons and the other is used the answer weak visibility queries. This is the first algorithm for the Art Gallery problem that both has theoretical guarantees and works arguably well in practice. The main question that we answer is whether the iterative algorithm is feasible in practice. We performed tests to measure the running time of the algorithm, and show that it does perform quite well practically. Additionally, several experiments using the practical implementation are discussed, answering questions about the running time of the algorithm such as the standard deviation, sensitivity to input parameters and workload distribution.