Chips on Wafers

A set of rectangles $\mathcal{S}$ is said to be grid packed if there exists a rectangular grid (not necessarily regular) such that every rectangle lies in the grid and there is at most one rectangle of $\mathcal{S}$ in each cell. The area of a grid packing is the area of a minimal bounding box that contains all the rectangles in the grid packing. We present an approximation algorithm that given a set $\mathcal{S}$ of rectangles and a real constant ε> 0 produces a grid packing of $\mathcal{S}$ whose area is at most (1 + ε) times larger than an optimal packing in polynomial time. If ε is chosen large enough the running time of the algorithm will be linear. We also study several interesting variants, for example the smallest area grid packing containing at least k ≤ n rectangles, and given a region $\mathcal{A}$ grid pack as many rectangles as possible within $\mathcal{A}$. Apart from the approximation algorithms we present several hardness results.