Advanced

Chips on wafers, or packing rectangles into grids

Andersson, Mattias LU ; Gudmundsson, J and Levcopoulos, Christos LU (2005) In Computational Geometry 30(2). p.95-111
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:
author
organization
publishing date
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
0925-7721
DOI
10.1016/j.comgeo.2004.05.006
project
VR 2002-4049
language
English
LU publication?
yes
id
d30225b2-e06d-4c2a-b1f6-7c0108824e1b (old id 258043)
date added to LUP
2007-08-07 10:51:37
date last changed
2017-01-01 06:38:22
@article{d30225b2-e06d-4c2a-b1f6-7c0108824e1b,
  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         = {0925-7721},
  keyword      = {computational geometry,approximation algorithms,packing rectangles},
  language     = {eng},
  number       = {2},
  pages        = {95--111},
  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},
}