Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations (Q1772125)

The paper deals with the area of art gallery whose main question can be stated as follows. What is the minimum number of guards (with a specified restriction of the scope of their vision) who can collectively monitor an art gallery shaped as a simple polygon with \(n\) vertices? A guard (a point) \(v\) is said to be a \(\pi\)-guard if the range of his vision is restricted to \(\pi\). Let \(H^v\) be the closed half-plane filled with the ``rays of vision from \(v\)''. If, at a reflex vertex \(v\), \(H^v\) faces inward and its boundary is collinear with one of the sides incident to \(v\), then the \(\pi\)-guard \(v\) is called an edge-aligned vertex \(\pi\)-guard. If there are no restrictions on the orientation of \(H^v\), the \(\pi\)-guard \(v\) is called a general vertex \(\pi\)-guard. The authors prove the following. 1. Any simple polygon with \(n\) vertices can always be monitored by \([n/2]\) general vertex \(\pi\)-guards. 2. Any simple polygon with \(n\) vertices can be always monitored by \([(2n-k)/3]\) edge-aligned vertex \(\pi\)-guards.