A Tight Lower Bound for Art Gallery Sensor Location Algorithms

Locating sensors in 2D can be often modelled as an Art Gallery problem. Tasks such as surveillance require observing or "covering" the interior of a polygon with a minimum number of sensors or "guards". Observing the boundaries of a polygonal environment is sufficient for tasks such as inspection and image based rendering. As interior covering, also Edge Covering (EC) is NP-hard, and no finite algorithm is known for its exact solution. A number of heuristics have been proposed for the approximate solution of this important problem, but their performances with respect to optimality is unknown. Therefore, a polygon specific tight lower bound for the number of sensors is very useful for assessing the performances of these algorithms. In this paper, we propose a new lower bound for the EC problem. It can be computed in reasonable time for environments with up to a few hundreds of edges. To evaluate its closeness to optimality, we compare it with a previously developed lower bound and with the solution provided by a recent incremental EC algorithm. Tests over hundreds of polygons with different number of edges show that the new lower bound is tight and outperforms the previous one.