Advanced

Chips on wafers

Andersson, Mattias LU ; Gudmundsson, J and Levcopoulos, Christos LU (2003) 8th International Workshop, WADS 2003 In Lecture Notes in Computer Science 2748. p.412-423
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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science
volume
2748
pages
412 - 423
publisher
Springer
conference name
8th International Workshop, WADS 2003
external identifiers
  • wos:000185605300036
ISSN
0302-9743
1611-3349
ISBN
978-3-540-40545-0
DOI
10.1007/978-3-540-45078-8_36
project
VR 2002-4049
language
English
LU publication?
yes
id
750fcc91-48ba-42a3-991a-cf7d1fccc00e (old id 299950)
date added to LUP
2007-08-22 12:14:23
date last changed
2018-05-29 09:39:47
@inproceedings{750fcc91-48ba-42a3-991a-cf7d1fccc00e,
  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    = {Lecture Notes in Computer Science},
  isbn         = {978-3-540-40545-0},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {412--423},
  publisher    = {Springer},
  title        = {Chips on wafers},
  url          = {http://dx.doi.org/10.1007/978-3-540-45078-8_36},
  volume       = {2748},
  year         = {2003},
}