Approximation algorithms for guarding holey polygons
Mohammad Hosseinzadeh Moghaddam, H Divdel, G Alipour · Journal of Fundamental and Applied Sciences · 2016
Guarding edges of polygons is a version of art gallery problem.The goal is finding the minimum number of guards to cover the edges of a polygon. This problem is NP-hard, and to our knowledge there are approximation algorithms just for simple polygons. In this paper we present two approximation algorithms for guarding polygons with holes.Keywords: guarding, approximation algorithm, vertex guard, edge guard