1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't have it with me right now, but if I recall correctly the solution (with proof) is given in this book. $\endgroup$ Jan 28 '13 at 16:35
  • $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Jan 28 '13 at 16:38
1
$\begingroup$

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.)
$\endgroup$
1
  • $\begingroup$ Is there by any chance an algorithm that finds, for an arbitrary gallery, the minimum number of guard required ? $\endgroup$ Jun 6 '15 at 17:37

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.