Approximation algorithms for art gallery problems in polygons

作     者：Ghosh, Subir Kumar 

作者机构：Tata Inst Fundamental Res Sch Comp Sci Bombay 400005 Maharashtra India 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2010年第158卷第6期

页      面：718-722页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [DCR83-51468] IBM 

主　　题：Approximation algorithms Computational geometry Art gallery problems Visibility polygons Minimum set cover Greedy algorithms 

摘      要：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)). (C) 2009 Elsevier B.V. All rights reserved.