Math @ Duke

Publications [#235570] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Shing, MT, Oriented aligned rectangle packing problem,
European Journal of Operational Research, vol. 62 no. 2
(1992),
pp. 210220, ISSN 03772217
(last updated on 2018/07/22)
Abstract: Given a collection R of n (= M × N) rectangles, we wish to pack it into M rows and N columns as the elements of an M × N matrix. The height of a row is defined to be the height of the tallest rectangle in that row, and the width of a column is defined to be the width of the widest rectangle in that column. The cost of a packing is the sum of the heights of the M rows plus the sum of the widths of the N columns. The oriented aligned rectangle packing problem is to find a packing with the minimum cost. In this paper we present an O(n) time algorithm and an O(n2) time algorithm for two nontrivial special cases. We also show how to extend the algorithms to handle other cost functions. © 1992.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

