Improved Approximation for Guarding Simple Galleries from the Perimeter

Details Improved Approximation for Guarding Simple Galleries from the Perimeter Improved Approximation for Guarding Simple Galleries from the Perimeter

2010-01-24

arxiv.org/abs/1001.4231v1

Computer Science

Computational Geometry

16 pages, 8 figures

Scientific paper

We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this epsilon-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon's vertices. If a finite set of potential guard locations is not specified, e.g. when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm's running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.

Affiliated with

Also associated with

No associations

Rating

Improved Approximation for Guarding Simple Galleries from the Perimeter 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 Improved Approximation for Guarding Simple Galleries from the Perimeter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Approximation for Guarding Simple Galleries from the Perimeter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-696732