A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon

Stav Ashur, Omrit Filtser, Matthew J. Katz

The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(\log n)$-approximation algorithm for placing as few g…