Krivulya G. Mathematical model and solution method for a covering problem of a polygonal area with a family of rectangles

The inquiry subject is a process of a rectangular covering of arbitrary polygonal areas. The research agenda is a mathematical and computer modeling of a covering of a disconnected compact canonical polygonal area with a given finite family of rectangles. The following methods are applied: the Ф- function and Г- function techniques; optimization method by a group of variables, Voronoi polygons; the simplex-method; the branch and bound algorithm; the decremental neighborhood method. The Г- function method is advanced. The mathematical model of the translational polygonal containment problem is first constructed when placement parameters and metric characteristics of the target area are variable. The mathematical model of the covering problem is first constructed using Г- function technique. Solution method of the translational polygonal containment problem is advanced. The solution method for the covering problem is first provided. The method allows us to reduce the covering problem to a sequence of linear programming problems. Truncation rules of unpromising nodes of a solution tree are first proposed. Computer programs have been developed. The programs may be used for covering problems which arise in telecommunications, flooding systems, air and space observing systems, fire safety and medicine. The results of studies has been implemented in the instruction process at the Kharkiv National University of Radio Electronics and Kharkiv National University of Internal Affairs.