INFORMATICS

Enumerating the maximum free rectangular areas

U. M. Bishenov, P. M. Ivanov

Institute of Computer Science and Problems of Regional Management of KBSC of RAS, Nal'chik

Abstract: The paper considers the problem of placing rectangular objects without overlap on a limited flat surface. A discrete model of the problem is constructed. New efficient algorithms have been obtained that use the method of cellular discretization of the problem with subsequent enumeration of all objects of interest. A complete characterization of the problem is given and an optimal algorithm for solving it is given.

Keywords: placement, maximum free rectangle, cellular discretization, discrete topology, algorithms, free space

UDC: 519.717