Covering Polygons with Rectangles

Abstract

A well-known and well-investigated family of hard optimization problems deals with nesting, i.e., the non-overlapping placing of polygons to be cut from a rectangle or the plane whilst minimizing the waste. Here we consider the in some sense inverse problem of a subsequent step in production technology: given a set of polygons in the plane and an axis-aligned rectangle (modeling a gripping device), we seek the minimum number of copies of the rectangle such that every polygon is completely covered by at least one copy of the rectangle. As motions of the given rectangle for obtaining the copies we investigate the cases of translation in x-direction, of arbitrary translation and of arbitrary translation combined with rotation. We give a generic algorithm for all three cases which leads to a polynomial-time algorithm for the first case. The other two cases are NP-hard so we introduce a rather straightforward algorithm for the second case and two different approaches to the third one. Finally, we give experimental results and compare them to the theoretical analysis done before.