8
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Which variations? $\endgroup$ Apr 26, 2012 at 13:55
  • $\begingroup$ 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! $\endgroup$ Apr 26, 2012 at 15:23
  • $\begingroup$ Chapter 3 of T S Michael, How to Guard an Art Gallery, might have some suggestions. $\endgroup$ Apr 26, 2012 at 22:59

1 Answer 1

12
$\begingroup$

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).

$\endgroup$
2
  • 2
    $\begingroup$ Did you mean $g=8$ (not 6)? $\endgroup$ Apr 26, 2012 at 13:23
  • $\begingroup$ Whoops! Typo :-). Thanks, Barry, repaired now. $\endgroup$ Apr 26, 2012 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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