Advertisement
Published in:
2010 | OriginalPaper | Chapter
Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments
Authors : Valentin E. Brimkov, Andrew Leach, Michael Mastroianni, Jimmy Wu
Published in: Advances in Visual Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Consider any real structure that can be modeled by a set of straight line segments. This can be a network of streets in a city, tunnels in a mine, corridors in a building, pipes in a factory, etc. We want to approximate a minimal number of locations where to place “guards” (either men or machines), in a way that any point of the network can be “seen” by at least one guard. A guard can see all points on segments it is on (and nothing more). As the problem is known to be NP-hard, we consider three greedy-type algorithms for finding approximate solutions. We show that for each of these, theoretically the ratio of the approximate to the optimal solution can increase without bound with the increase of the number of segments. Nevertheless, our extensive experiments show that on randomly generated instances, the approximate solutions are
always
very close to the optimal ones and often are, in fact, optimal.