Understanding of geometric visibility in polygons

Geometric covering problems have been a focus of research for decades. Most variants of the problem are NP-hard, and therefore most research on geometric set cover focuses on designing polynomial-time approximation algorithms whose approximation ratio is as good as possible. This problem is classically referred to as the art gallery problem as an art gallery can be modeled as a polygon and the points placed by an algorithm represent cameras that can "guard" the art gallery. This has been one of the most well-known problems in computational geometry for many years, yet still to this date the best polynomial-time approximation algorithm for this problem is the O(log n) approximation algorithm that uses no geometric information. The key issue is a fundamental lack of understanding of the combinatorial structure of visibility inside simple polygons. In this thesis, first we give a characterization of the visibility graphs of pseudo-polygons. We identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to O'Rourke and Streinu's vertex-edge characterization. Second, we improve the VC- dimension of the visibility on the boundary of a monotone polygon lower bound from 4 to 6, and we improve the upper bound from 7 to 6. Moreover we improve the upper bound on the VC-dimension of the visibility on the boundary of a simple polygon to 6.