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.
Preprint version: Postscript, PDF
Back