Computer Science – Computational Geometry
Scientific paper
2011-01-17
Computer Science
Computational Geometry
18 pages, 10 figures
Scientific paper
For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of P's vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into O(n^4) cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of set cover and solved in O(n^5) time with a greedy O(log n)-approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only O(n^3) cells, improving the running time of the algorithm to O(n^4) for simple polygons. In this paper we show that, since minimum visibility decompositions for simple polygons have only O(n^2) cells of minimal visibility (Bose et al., 2000), the running time of the algorithm can be further improved to O(n^3). This result was obtained independently by Jang and Kwon (2011). We extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only O((h+1)n^3) cells and only O((h+1)^2 n^2) cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of O(log log(opt)) for simple polygons and O((1+\log((h+1))) log(opt)) for polygons with holes.
No associations
LandOfFree
Fast Vertex Guarding for Polygons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Vertex Guarding for Polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Vertex Guarding for Polygons will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-286742