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?

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

This is known as the Art gallery problem.

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.

  • $\begingroup$ so, is it just mere observation? Not that it's a bad approach, but is there a proof not using the 3-coloring method? $\endgroup$ – V Shreyas Jun 27 '14 at 12:22
  • $\begingroup$ I believe all of those facts I stated have been proven. You can probably find a proof online if you search for one. $\endgroup$ – JimmyK4542 Jun 27 '14 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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