Decomposing complex patterns into standardized geometric areas is essential for many pattern recognition and CAD applications 7"2. The decomposition of polygons into rectangles is studied in the paper. An algorithm that covers convex polygons by rectangles is presented. The algorithm works in two stages: interior covering and boundary covering. For a given convex polygon, the algorithm covers the interior ot the polygon by a few rectangles first, then covers the remaining areas by rectangles constructed along the edges of the polygon. No searching for uncovered areas is required. The performance of this algorithm is extremely efficient. It takes only one seventh of the time required by a previous algorithm to cover a convex polygon with about the same number of rectangles.
geometry, pattern recognition, polygon decomposition
The traditional optical method of reticle generation with repeated steps is the most commonly used method in generating masks for microcircuits. The reticle is generated on a photographic plate by exposing areas on the plate corresponding to the integrated circuit (IC) design. Polygons of the IC designs have to be decomposed into rectangles so that the pattern generator can be directed to expose the corresponding areas of the photographic plate ~' 4. The number of rectangles should be small so that the mask-making process can be carried out efficiently. This is equivalent to the problem of decomposing a polygon into minimum number of rectangles.
There are two basic types of decompositions:
β’ partition, which disallows overlapping of component parts β’ covering, which allows overlapping parts Only rectilinear polygons can always allow a partition S.
The partition problem of rectilinear polygons has been extensively studied ~-14. Not much work has been done on the covering of polygons by rectangles. The only known result is an algorithm proposed by Hegedus 9. This algorithm covers a simple polygon by first constructing maximum rectangles along the edges of