The matrix decomposition method of multicoherent polygon into the set of rectangular areas of minimum capacity

Abstract

The problem of decomposition of multicoherent orthogonal polygons into the set of rectangular areas of minimum capacity to which many problems of optimal placing and covering in areas of complex structure are reduced is considered. In the given statement sizes of the boxes sides are arbitrary and their overlapping is forbidden. The problem is NP-hard and for decomposition designing the heuristic method based on the matrix method of polygon division into rectangular areas is offered. It is offered to search for the optimal solution on the base of evolutionary algorithm.