View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Solving the Art Gallery Problem in Iterations

        Thumbnail
        View/Open
        S.B.Hengeveld_Final_Final_Thesis.pdf (3.593Mb)
        Publication date
        2020
        Author
        Hengeveld, S.B.
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/37128
        Collections
        • Theses
        Utrecht university logo