A set of rectangles 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 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 S of rectangles and a real constant e > 0 produces a grid packing of S whose area is at most (1 + e) times larger than an optimal grid packing in polynomial time. If e 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 A grid pack as many rectangles as possible within A. Apart from the approximation algorithms we present several hardness results.
['Mattias Andersson', 'Joachim Gudmundsson', 'Christos Levcopoulos']
Chips on wafers, or packing rectangles into grids