Computer-Aided Proofs for the VC-dimension of Art Gallery Variants

Visibility problems are fundamental to computational geometry, and many versions of geometric set cover where coverage is based on visibility have been considered. In most settings, points can see "infinitely far" so long as visibility is not "blocked" by some obstacle. In many applications, this may be an unreasonable assumption. We consider a new model of visibility where no point can see any other point beyond a sight radius ρ. We consider this visibility model in the context of art gallery variants. We show that the VC-dimension of limited visibility terrains is exactly 7. We give lower bound construction that shatters a set of 7 points, and we prove that shattering 8 points for limited visibility terrains is not possible. We also prove a collection of lemmas about the structure of visibility and that help finding the VC-dimension of limited visibility on the boundary of simple polygons.

We also consider the VC-dimension of visibility on the boundary of simple polygons under this limited visibility model. That is, we restrict all guards/viewpoints to be on the boundary of the simple polygon. We show that the VC-dimension under the limited visibility model is exactly 8. That is, we give an example of a simple polygon with 8 "guards" on the boundary such that every one of the 2⁸ subsets of the 8 guards has a "viewpoint" that sees exactly the guards in the subset. We then show that this is not possible with any set of 9 guards.

Finally, we consider the problem of lowering the upper bound on the VC-dimension of the classic art gallery problem (no limited visibility constraints), and the guards and viewpoints can lie anywhere in the interior of the polygon. This problem has not seen an improvement in a decade. We extend our code to address this problem, relying on counterclockwise systems defined by Knuth to discretize the set of possible polygons. We give a dynamic programming approach for finding all of the ways that certain guard and viewpoint sets can be placed while satisfying their visibility requirements.