8
$\begingroup$

I am stuck on a problem related to art galleries. It is problem $12$ in the chapter about art galleries in How to Guard an Art Gallery and Other Discrete Mathematical Adventures by T.S. Michael (I slightly edited the question, mostly to introduced notations $k$ and $n$):

Post $k=10$ guards in a particular art gallery with $n=17$ walls so that the entire gallery is protected, but the dismissal of any guard leaves some part of the gallery unprotected.

The difficulty is clearly that the art gallery in the problem is an unknown that should be determined. I tried many examples of galleries with $17$ walls but so far, I can only find an example for the simpler problem with $k=8$ (a star-shaped gallery).

Any idea?

Background if you don't know about art galleries but want to try to solve the problem:

  1. An art gallery with $n$ walls is represented by a nonconvex polygon with $n$ edges.
  2. A guard is represented by a point. The guard can be positioned anywhere in the gallery, including along a wall or at a vertex.
  3. Guards cannot move, but can see all around them (at once!). They A point $p$ in the interior of the gallery is seen by a guard $g$, if $[p,q)$ is contained in the interior of gallery.
  4. A gallery is protected if any point in its interior is seen by at least one guard.
$\endgroup$
2
  • 3
    $\begingroup$ For more background, see also Wikipedia's "art gallery problem" entry, which mentions that the minimum number of guards required to guard an $n$-walled gallery is $\lfloor n/3\rfloor$. For this problem's gallery, that minimum is $5$, so it's curious that the problem asks for the placement of twice as many guards as are necessary. $\endgroup$
    – Blue
    Sep 12, 2018 at 4:48
  • $\begingroup$ @Blue: I don't see why that's curious. It could well be that you can guard the entire gallery with $5$ well-placed guards but you can also place $10$ guards badly such that none of them is redundant. $\endgroup$
    – joriki
    Sep 12, 2018 at 7:35

1 Answer 1

Reset to default
5
$\begingroup$

Here is a solution with $k = 10, n = 17$: a solution with k = 10, n = 17

I'll try to explain the procedure of how I constructed this image which could be used to create some other cases of n and k.

I realized that I could construct a polygon with a series of "pieces". I could place guards on a piece without these guards being made redundant by guards from different piece, so the pieces are independent from each other. I could then chain the pieces together any way I want.

My example polygon has 2 types of pieces: 1) A spike (one of these is colored yellow/orange) 2) A spike with a flat edge on the left side (one of these is colored green)

The spike piece uses 2 edges and allows 1 guard. The second type of piece uses 3 edges and allows 2 guards. Additionally I need an extra edge to connect my chain. By observing this I could count the number of edges in a polygon made up of x spikes, y flat-spikes, plus an extra edge to connect the ends of the chain with this equation:

$n = 17 = 2x + 3y + 1$

And similarly the number of guards that each chain allows:

$k = 10 = x + 2y$

Solve the system of equations for number of spikes = x and number of spike-edges = y. Solving this system of equations with different values of k and n would allow some other general answers.

$\endgroup$
1
  • 1
    $\begingroup$ Great answer, and welcome to Math.SE! $\endgroup$
    – Taladris
    Sep 19, 2018 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .