An exact algorithm for coverage problem with a single rectangle

We consider positioning a target rectangle on two-dimensional plane to partially cover a set of existing rectangular areas (requests) to maximize total coverage reward. Important applications are in camera surveillance and resource allocation in homeland security and disaster management. We introduce a reduced solution space and present a novel branch-And-bound exact algorithm. Branching is done using a clustering scheme. Our computational results show that in many cases our approach significantly outperforms the existing plateau vertex traversal and brute force algorithms, especially for problems with many requests appearing in clusters over a large region and those with heterogeneous request reward rates.

An exact algorithm for coverage problem with a single rectangle Conference Paper