Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420438 | Discrete Applied Mathematics | 2010 | 5 Pages |
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 nn vertices. For simple polygons, approximation algorithms for both problems run in O(n4)O(n4) time and yield solutions that can be at most O(logn)O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn)O(logn), but the running time of the algorithms increases by a factor of nn to O(n5)O(n5).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Subir Kumar Ghosh,