Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons

Shouvik Mondal, Udvas Das, Sasanka Roy

The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon. It is $\exists \mathbb{R}$-complete, hence NP-hard. We show that for a particular class of…