The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Chips on wafers, or packing rectangles into grids

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

95-111

Publication/Series

Computational Geometry

Volume

30

Issue

2

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • computational geometry
  • approximation algorithms
  • packing rectangles

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0925-7721