Chips on wafers
(2003) 8th International Workshop, WADS 2003 In Lecture Notes in Computer Science 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:
https://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
 host publication
 Algorithms and data structures
 series title
 Lecture Notes in Computer Science
 volume
 2748
 pages
 412  423
 publisher
 Springer
 conference name
 8th International Workshop, WADS 2003
 conference location
 Ottawa, Ontario, Canada
 conference dates
 20030730  20030801
 external identifiers

 wos:000185605300036
 scopus:35248817850
 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
 20160401 12:08:30
 date last changed
 20210217 03:22:47
@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}, series = {Lecture Notes in Computer Science}, title = {Chips on wafers}, url = {http://dx.doi.org/10.1007/9783540450788_36}, doi = {10.1007/9783540450788_36}, volume = {2748}, year = {2003}, }