Find the minimal number of guard points of polygon

Question

Given a polygon with $n$ vertices, what is the minimal number of points inside the polygon such that for each interior point there exists at least one point such that the segment between them lies inside the polygon?

If the polygon is convex, one point is enough (any point inside the polygon).

Answer 1

The number is $\displaystyle \left\lfloor\frac{n}3\right\rfloor$, meaning that this number always suffices, and there are polygons for which it is needed. This is Chvátal's Art Gallery Theorem from 1975. The question was originally asked by Klee in 1973.

The necessity is not too hard, the typical example is a "comb", and can be seen in the first two linked references below. Or see this MO question.

Wikipedia includes a sketch of the sufficiency. A beautiful exposition of the result, including an explanation on how some natural approaches to the proof fail, can be found in the book "Art Gallery Theorems and Algorithms", by Joseph O'Rourke, Oxford University Press, 1987, which can be downloaded from Joseph's website. See pages 1-9; the book presents both Chvátal's argument, and an easier later proof due to Fisk. Algorithms and complexity issues are discussed in the following pages. The argument can also be found in Aigner-Ziegler "Proofs from THE BOOK".

Very roughly, Fisk's argument is as follows:

• One starts by triangulating the polygon by adding (internal) diagonals between vertices. (This step actually requires a bit more care than one would expect).
• The graph of a triangulated polygon can be 3-colored. (This is the most delicate step.)
• Of course, one of the three colors is used at most one-third of the time (that is, at most $\displaystyle \left\lfloor\frac{n}3\right\rfloor$ vertices use this color). Place guards on these vertices. (A small perturbation verifies that we can replace these guards by nearby guards in the interior of the polygon.)