Publisher
The University of Arizona.Rights
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.Abstract
Covering a polygon by a set of rectangles has many applications in the VLSI CAD area. In this thesis, a new efficient algorithm to cover a polygon has been developed. It is not limited by the rectilinear restriction, but each inner angle of the polygon is at least 90 degrees. The algorithm has two phases. The first phase decomposes a non-rectilinear polygon P(n) into two parts. One part is a rectilinear polygon P(r), and the other part consists of the rest of P(n). This phase also generates a set of rectangles covering the non-rectilinear part. The time complexity of this phase is O(b∗n), where b is the number of oblique edges and n is the number of vertices in P(n). The second phase finds an overlapping rectangle cover for the rectilinear part P(r) by generating a non-overlapping cover first. The complexity of this phase is O(klog (k) + r + m²), where k is the number of inversions, r the number of the vertices in P(r), and m the size of the non-overlapping rectangle cover. The algorithm has been implemented and experimental results are provided to show the effectiveness of our approach.Type
textThesis-Reproduction (electronic)
Degree Name
M.S.Degree Level
mastersDegree Program
Graduate CollegeElectrical and Computer Engineering