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:
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
- 2003-07-30 - 2003-08-01
- external identifiers
-
- wos:000185605300036
- scopus:35248817850
- 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
- 2016-04-01 12:08:30
- date last changed
- 2024-01-08 09:50:52
@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 = {{Algorithms and data structures}},
isbn = {{978-3-540-40545-0}},
issn = {{0302-9743}},
language = {{eng}},
pages = {{412--423}},
publisher = {{Springer}},
series = {{Lecture Notes in Computer Science}},
title = {{Chips on wafers}},
url = {{http://dx.doi.org/10.1007/978-3-540-45078-8_36}},
doi = {{10.1007/978-3-540-45078-8_36}},
volume = {{2748}},
year = {{2003}},
}