Main Article Content

Approximation algorithms for guarding holey polygons

M.H. Moghaddam
H Divdel
G Alipour


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

Journal Identifiers

print ISSN: 1112-9867