scientific article; zbMATH DE number 3872705
[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)].
- Covering simply connected regions by rectangles
- Close approximations of minimum rectangular coverings
- Approximate guarding of monotone and rectilinear polygons
- Covering points with minimum/maximum area orthogonally convex polygons
- The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
- scientific article; zbMATH DE number 5369649 (Why is no real title available?)
- scientific article; zbMATH DE number 3918386 (Why is no real title available?)
- An algorithm for covering polygons with rectangles
- scientific article; zbMATH DE number 4049039 (Why is no real title available?)
- scientific article; zbMATH DE number 29609 (Why is no real title available?)
- scientific article; zbMATH DE number 1076151 (Why is no real title available?)
- scientific article; zbMATH DE number 4121435 (Why is no real title available?)
- scientific article; zbMATH DE number 3893101 (Why is no real title available?)
- scientific article; zbMATH DE number 5025945 (Why is no real title available?)
- Close approximations of minimum rectangular coverings (extended abstract)
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)