Art Gallery Problem - is covering the edges enough?

Question

The question is quite straight-forward but I can't seem to find the correct keywords to get my answer on the internet.

For those who are not familiar with the problem, given a polygon P we are asked to find the minimum number of guards which together can see the whole polygon ( assuming that each guard has a 360 field of view ) . An example of a solution can be seen in the following picture in which two guards suffice :

Now, my question is : If the guards can see all the edges of the polygon (from its interior of course), do they see the whole polygon?

This could do wonders for my solution as I wouldn't have to bother about the guards being able to see the interior of the polygon.

Yes. If you can see an edge, you can see its endpoints so if you can see all edges you can see the entire polygon. — John Douma, Jul 05 '19 at 17:29
Well, that means you can see the perimeter of the polygon but not necessarily the interior space of the polygon. It makes sense to me as well, but I've seen some weird polygons when it comes to the "exception" of the rule in computational geometry. For example, a polygon with holes inside might make this more complicated. — John Katsantas, Jul 05 '19 at 17:35

score 4 · Accepted Answer · answered Jul 10 '19 at 00:15

4

No. On the picture below guards in green corners can see the whole perimeter but can not see the region with red points.

answered Jul 10 '19 at 00:15

datjko

181

It would seem that this is not quite what the OP meant. I would not say that the edges are "covered" by your example. – N. Owad Jul 10 '19 at 00:33
@N.Owad why not? Each point of each edge is observable by at least one guard. – datjko Jul 10 '19 at 23:46
Ah, my mistake. I did not understand your diagram when I first looked at this post. – N. Owad Jul 16 '19 at 11:07

Art Gallery Problem - is covering the edges enough?

1 Answers1