A new lower bound for evaluating the performances of sensor location algorithms

Locating sensors in 2D can be 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 (IC, Interior Covering). Edge Covering (EC) is sufficient for tasks such as inspection or image based rendering. As IC, also EC is NP-hard, and no finite algorithm is known for its exact solution. A number of heuristics have been proposed for EC, but their performances with respect to optimality are unknown. Recently, a lower bound for the cardinality of the optimal EC solution, specific of a given polygon, has been proposed. It allows assessing the performances of approximate EC sensor location algorithms. In this paper, we propose a new lower bound. It is always greater than, or equal to the previous, and can be computed in reasonable time for environments with up to a few hundreds of edges. Tests over hundreds of polygons using a recent incremental EC algorithm show that the gap between the cardinality of the solution provided by the algorithm and the new lower bound is substantially reduced, and then the new lower bound outperforms the previous one.