Approximation algorithms for guarding holey polygons

  • M.H. Moghaddam
  • H Divdel
  • G Alipour
Keywords: guarding, approximation algorithm, vertex guard, edge guard

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

Published
2016-09-01

Journal Identifiers


eISSN: 1112-9867