Chips on wafers, or packing rectangles into grids
(2005) In Computational Geometry 30(2). p.95111 Abstract
 A set of rectangles S is said to be gridpacked 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 epsilon constant epsilon > 0 produces a grid packing of S whose area is at most (1 + epsilon) times larger than an optimal grid packing in polynomial time. If epsilon 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... (More)
 A set of rectangles S is said to be gridpacked 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 epsilon constant epsilon > 0 produces a grid packing of S whose area is at most (1 + epsilon) times larger than an optimal grid packing in polynomial time. If epsilon 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 less than or equal to 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/258043
 author
 Andersson, Mattias ^{LU} ; Gudmundsson, J and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2005
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 computational geometry, approximation algorithms, packing rectangles
 in
 Computational Geometry
 volume
 30
 issue
 2
 pages
 95  111
 publisher
 Elsevier
 external identifiers

 wos:000226155000003
 scopus:10044253053
 ISSN
 09257721
 DOI
 10.1016/j.comgeo.2004.05.006
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 d30225b2e06d4c2ab1f67c0108824e1b (old id 258043)
 date added to LUP
 20070807 10:51:37
 date last changed
 20170101 06:38:22
@article{d30225b2e06d4c2ab1f67c0108824e1b, abstract = {A set of rectangles S is said to be gridpacked 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 epsilon constant epsilon > 0 produces a grid packing of S whose area is at most (1 + epsilon) times larger than an optimal grid packing in polynomial time. If epsilon 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 less than or equal to 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.}, author = {Andersson, Mattias and Gudmundsson, J and Levcopoulos, Christos}, issn = {09257721}, keyword = {computational geometry,approximation algorithms,packing rectangles}, language = {eng}, number = {2}, pages = {95111}, publisher = {Elsevier}, series = {Computational Geometry}, title = {Chips on wafers, or packing rectangles into grids}, url = {http://dx.doi.org/10.1016/j.comgeo.2004.05.006}, volume = {30}, year = {2005}, }