MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

I think this will not be a "big-list" (as per your tag), because in some sense all examples will be variations on the same theme. Nevertheless, here is my offering:
     Saw Tooth Wheel
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.

Addendum. Now that I see Gray's motivation, it may not be inappropriate to mention that these saw-tooth-like polygons achieve the current best lowerbounds on the transmitter problem he mentions, as I described in "Computational Geometry Column 52" (Fig. 2).

share|cite|improve this answer
Did you mean $g=8$ (not 6)? – Barry Cipra Apr 26 '12 at 13:23
Whoops! Typo :-). Thanks, Barry, repaired now. – Joseph O'Rourke Apr 26 '12 at 14:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.