Guarding Polygons with Mutually Visible π-Guards- MSc Thesis Defense by: Ali Nakhaeisharif

The School of Computer Science is pleased to present…

Guarding Polygons with Mutually Visible -Guards

Date: Tuesday, April 29^th, 2025

Time:  12:00 PM

Location: Essex Hall Room 122

We study a version of the art gallery problem in which, for a given simple polygon,  we want to place the minimum number of guards with  the field of view at the vertices such that they guard the entire polygon, and for each guard  there is a guard  that  and  is mutually visible. Let  be the minimum number of such guards over all polygons of size . We show that . We define  Analogously for orthogonal polygons with  vertices, and show that . The lower bounds are existential in the sense that there are polygons that need this many guards. Additionally, through a reduction from the 3- problem, we prove that determining the minimum number of -guards with mutual visibility is -hard.