# Find the minimal number of guard points of polygon

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).

• I don't have it with me right now, but if I recall correctly the solution (with proof) is given in this book. Jan 28 '13 at 16:35
• For a given polygon (as opposed to just the worst case over all polygons of size $n$) this is well-known to be NP-hard, even to approximate. See Wikipedia. Jan 28 '13 at 16:38

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.
• 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.)