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 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references