Fast Approximation Algorithms for Art Gallery Problems in Simple Polygons

Details Fast Approximation Algorithms for Art Gallery Problems in Simple Polygons Fast Approximation Algorithms for Art Gallery Problems in Simple Polygons

2011-01-07

arxiv.org/abs/1101.1346v1

Computer Science

Computational Geometry

Scientific paper

We present approximation algorithms with O(n^3) processing time for the minimum vertex and edge guard problems in simple polygons. It is improved from previous O(n^4) time algorithms of Ghosh. For simple polygon, there are O(n^3) visibility regions, thus any approximation algorithm for the set covering problem with approximation ratio of log(n) can be used for the approximation of n vertex and edge guard problems with O(n^3) visibility sequence. We prove that the visibility of all points in simple polygons is guaranteed by covering O(n^2) sinks from vertices and edges : It comes to O(n^3) time bound.

Affiliated with

Also associated with

No associations

Rating

Fast Approximation Algorithms for Art Gallery Problems in Simple 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 Approximation Algorithms for Art Gallery Problems in Simple Polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Approximation Algorithms for Art Gallery Problems in Simple Polygons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-483346