# Polygons that are hard to guard

Given an $n$-vertex polygonal 'art gallery' $P$ in the plane, it is possible to cover the interior of $P$ by placing 'guards' at (at worst) $\lfloor n/3\rfloor$ of the vertices of $P$. That this is sufficiently many can be shown elegantly by triangulating $P$, then $3$-colouring this triangulation and placing guards at the vertices with the least common colour.

For a lower bound only a single family of examples is needed, and the standard is the $n$-pronged comb (or crown) which has $3n$ vertices and requires one guard for each prong. However, in considering variations on the art gallery problem it can be the case that the comb is easier to guard, and thus other families (which are harder in this new context) are required. So, is there (or can we construct in comments) a big list of 'hard to guard' polygons - that is, $n$-vertex polygons for which $\lfloor n/3 \rfloor$ guards are required - that could be used as starting points for considering variations?

-
Which variations? –  Felix Goldberg Apr 26 '12 at 13:55
At the moment the variation I'm playing with is to allow guards to see through a single wall (the k=1 case of 'k-transmitters'), but to require that they be placed in the exterior of $P$. For the upper bound this is not much of a variation- if you can $0$-guard at $l$ vertices, you can $1$-guard at $l$ external locations by pushing the guards just outside. But for the lower bound I haven't yet drawn something that I couldn't get away with one less guard, since they can see into two prongs or spikes or fiddly bit I add. But I suspect this could just be inexperience on my part! –  Gray Taylor Apr 26 '12 at 15:23
Chapter 3 of T S Michael, How to Guard an Art Gallery, might have some suggestions. –  Gerry Myerson Apr 26 '12 at 22:59

Let $x$ be a spike tip, and $V(x)$ the set of points that see $x$. Notice these $V(x)$ regions are disjoint for the 8 spike tips. Therefore each tip requires its own guard, and so this shape requires $n/3$ guards.
Did you mean $g=8$ (not 6)? –  Barry Cipra Apr 26 '12 at 13:23