Approximation algorithms for art gallery problems in polygons

摘要

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n(4)) time and yield solutions that can be at most O(log n) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(log n), but the running time of the algorithms increases by a factor of n to O(n(5)).