Covering a polygonal region by rectangles
Authors: G. Scheithauer, Y. G. Stoyan, T. Romanova, A. Krivuly
Computational Optimization and Applications (online May 2009)
The problem of covering a compact canonical
polygonal region, called target region,
with a finite family of rectangles is considered.
Tools for mathematical modeling of the problem are provided.
Especially, a function, called $\Gamma$-function,
is introduced which indicates
whether the rectangles with respect to their configuration form a cover
of the target region or not.
The construction of the $\Gamma$-function is similar to that of $\Phi$-functions
which have been proved to be an efficient tool
for packing problems.
A mathematical model of the covering problem
based on the $\Gamma$-function is proposed
as well as a solution strategy.
The approach is illustrated by an example.