K-vertex guarding simple polygons

A polygon P is called k-vertex guardable if there is a subset G of the vertices of P such that each point in P is seen by at least k vertices in G. For the main results of this paper, it is shown that the following number of vertex guards is sufficient and sometimes necessary to k-vertex guard any simple n-gon P without holes: ⌊2n/3⌋ are needed for k=2 if P is any n-gon and ⌊3n/4⌋ are needed for k=3 if P is any convexly quadrilateralizable n-gon. The proofs for both of the results yield algorithms with O(n2) runtimes.