PROMOTING ACCESS TO AFRICAN RESEARCH

Journal of Fundamental and Applied Sciences

Log in or Register to get access to full text downloads.

Remember me or Register



Approximation algorithms for guarding holey polygons

M.H. Moghaddam, H Divdel, G Alipour

Abstract


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




http://dx.doi.org/10.4314/jfas.v8i3s.129
AJOL African Journals Online