Hybrid Algorithms for Scheduling Sensors for Guarding Polygonal Domains
Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell · 2014
The art gallery problem models one aspect of optimally placing sensors to do visibility coverage in geometric domains. We dene and solve a new version of this problem in which each guard/sensor can be functional only for a limited period of time (e.g. due to limited battery life), and the task is to schedule sets of sensors within the domain to maximize the total time that the domain is covered. We present an optimal (but rather slow) algorithm and an approximating heuristic for the problem. We show how these algorithms could be combined to achieve optimal results more eciently. We implemented both solutions and experimented with many dierent input sets. Our experiments verify that our hybrid technique signicantly decreases the running time of the exact algorithm, while maintaining optimality.