Ghosh, Subir Kumar (2010) Approximation algorithms for art gallery problems in polygons Discrete Applied Mathematics, 158 (6). pp. 718-722. ISSN 0166-218X
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/j.dam.2009.12.004
Abstract
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(n4) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n5).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Approximation Algorithms; Computational Geometry; Art Gallery Problems; Visibility Polygons; Minimum Set Cover; Greedy Algorithms |
| ID Code: | 76285 |
| Deposited On: | 31 Dec 2011 08:58 |
| Last Modified: | 31 Dec 2011 08:58 |
Repository Staff Only: item control page
