Rectangle packing is a

packing problem Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few cont ...

where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.

Packing identical rectangles in a rectangle

In this variant, there are multiple instances of a single rectangle of size (''l'',''w''), and a bigger rectangle of size (''L'',''W''). The goal is to pack as many small rectangles as possible into the big rectangle without overlap between any rectangles (small or large). Common constraints of the problem include limiting small rectangle rotation to 90° multiples and requiring that each small rectangle is

orthogonal In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...

to the large rectangle. This problem has some applications such as loading of boxes on pallets and, specifically,

woodpulp Pulp is a lignocellulosic fibrous material prepared by chemically or mechanically separating cellulose fibers from wood, fiber crops, waste paper, or rags. Mixed with water and other chemical or plant-based additives, pulp is the major raw ma ...

stowage. As an example result: it is possible to pack 147 small rectangles of size (137,95) in a big rectangle of size (1600,1230).

Packing identical squares in a rectilinear polygon

Given a

rectilinear polygon A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons. In many cases another definition is ...

(whose sides meet at right angles) ''R'' in the plane, a set ''S'' of points in ''R'', and a set of identical squares, the goal is to find the largest number of non-overlapping squares that can be packed in points of ''S''. Suppose that, for each point ''p'' in ''S'', we put a square centered at ''p''. Let ''G''_S be the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of ...

of these squares. A square-packing is equivalent to an