Covering Polygons with Rectangles

Abstract

A well-known and well-investigated family of hard op- timization problems concerns variants of the cutting stock or nesting problem, i.e. the non-overlapping placing of polygons to be cut from a rectangle or the plane whilst minimizing the waste. Here we consider an in some sense inverse problem. Concretly, given a set of polygons in the plane, we seek the minimum number of rectangles of a given shape such that every polygon is covered by at least one rectangle. As mo- tions of the given rectangle we investigate the cases of translation and of translation combined with rota- tion.