scientific article; zbMATH DE number 3872705

From MaRDI portal
Publication:3339306





[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)].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3339306)