Fast Vertex Guarding for Polygons

Abstract. For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of P ’s vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into O n4 cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of set cover and solved in O n5 time with a greedy O(logn)-approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only O n3 cells, improving the running time of the algorithm to O n4 for simple polygons. In this paper we show that, since minimum visibility decompositions for simple polygons have only O n2 cells of minimal visibility (Bose et al., 2000), the running time of the algorithm can be further improved to O n3. This result was obtained independently by Jang and Kwon (2011). We extend the result of Bose et al. to polygons with holes, show-ing that a minimum visibility decomposition of a polygon with h holes has only