Chips on wafers
(2003) 8th International Workshop, WADS 2003 In Algorithms and data structures 2748. p.412423 Abstract
 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 epsilon > 0 produces a grid packing of S whose area is at most (I + epsilon) times larger than an optimal 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... (More)
 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 epsilon > 0 produces a grid packing of S whose area is at most (I + epsilon) times larger than an optimal 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/299950
 author
 Andersson, Mattias ^{LU} ; Gudmundsson, J and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2003
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Algorithms and data structures
 volume
 2748
 pages
 412  423
 publisher
 Springer
 conference name
 8th International Workshop, WADS 2003
 external identifiers

 wos:000185605300036
 ISSN
 03029743
 16113349
 ISBN
 9783540405450
 DOI
 10.1007/9783540450788_36
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 750fcc9148ba42a3991acf7d1fccc00e (old id 299950)
 date added to LUP
 20070822 12:14:23
 date last changed
 20160419 14:56:48
@inproceedings{750fcc9148ba42a3991acf7d1fccc00e, abstract = {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 epsilon > 0 produces a grid packing of S whose area is at most (I + epsilon) times larger than an optimal 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}, booktitle = {Algorithms and data structures }, isbn = {9783540405450}, issn = {03029743}, language = {eng}, pages = {412423}, publisher = {Springer}, title = {Chips on wafers}, url = {http://dx.doi.org/10.1007/9783540450788_36}, volume = {2748}, year = {2003}, }