# Area swept by vertex angles in an irregular polygon.

Given any general n-gon, what is the minimum number of vertex angles that sweep the whole area of the polygon?

That is to say, what should be the least number of vertices a person has to stand at in order to look at the whole area of the n-gon?

• Have you read this?: en.wikipedia.org/wiki/Art_gallery_problem – JimmyK4542 Jun 26 '14 at 5:09
• thank you so much! I wish I could upvote your comment. – V Shreyas Jun 26 '14 at 5:22
• also, is there a simpler proof than using dual graphs? – V Shreyas Jun 26 '14 at 6:16
• @JimmyK4542: Do you want to turn that comment into an answer, providing the link and a short summary? – MvG Jun 26 '14 at 9:03
• yes, i'd love to see that! – V Shreyas Jun 26 '14 at 11:52

For a simple $n$-gon, it has been proven that you can always select a set of $\left\lfloor\tfrac{n}{3}\right\rfloor$ vertices such that every point in the $n$-gon is viewable from one of these vertices. There are simple $n$-gons for which selecting $\left\lfloor\tfrac{n}{3}\right\rfloor$ vertices is necessary, that is we cannot select a smaller set of vertices, and still view every point from one of the selected vertices. For example, in the polygon shown in the first image here, no camera can see more than one of the triangular prongs, so $\left\lfloor\tfrac{n}{3}\right\rfloor$ vertices are needed. You can create an example for any $n = 3k$ by having $k$ prongs instead of $4$. For any $n = 3k+1$ or $n = 3k+2$, use $k$ prongs and chop off $1$ or $2$ of the bottom corners.
There are other extensions of this problem, for which nice results are known. If all the angles in the $n$-gon are $90^{\circ}$ or $270^{\circ}$, then only $\left\lfloor\tfrac{n}{4}\right\rfloor$ vertices are needed. Also, if a simple $n$-gon has $h$ interior "holes" for which we cannot see through, then $\left\lfloor\tfrac{n+h}{3}\right\rfloor$ vertices are needed.