No label defined (Q3339306)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3872705
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3872705 |
Statements
1984
0 references
rectangular covering
0 references
simple polygons
0 references
convex polygons
0 references
lower bound
0 references
upper bound
0 references
0.9186009764671326
0 references
[For the entire collection see Zbl 0533.00025.] In the fabrication of masks for integrated circuits, it is desirable to replace the polygons comprising the layout of a circuit with as small as possible number of rectangles. Let Q be the set of all simple polygons with interior angles \(\geq 90\) degrees. Given a polygon \(P\in Q\), let \(\theta\) (P) be the minimum number of (possibly overlapping) rectangles lying within P necessary to cover P, and let r(P) be the ratio between the length of the longest edge of P and the length of the shortest edge of P. For every natural \(n\geq 5\), and k, a uniform polygon \(P_{n,k}\) with n corners is constructed such that \(r(P_{n,k}) \geq k\) and \(\theta (P_ n)=\Omega (n \log \log (r(P_{n,k}))).\) On the other hand, by modifying a known heuristic it is shown that for all convex polygons P in Q with n vertices \(\theta (P)=O(n \log (r(P))).\) Recently, the above lower bound has been improved to \(\Omega\) (n log(r\((P{}_{n,k})))\) and the above upper bound generalized to include also non-convex polygons, in both cases by the first author [see ''On covering regions with minimum number of rectangles'', Proc. Int. Worksh. VLSI, Alg. and Arch., Amalfi/Italy (1984)].
0 references