Persistent Link:
http://hdl.handle.net/10150/291443
Title:
Efficient covering of general polygons by rectangles
Author:
Hsu, Yu-Cheng, 1966-
Issue Date:
1990
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:
text; Thesis-Reproduction (electronic)
Keywords:
Computer Science.; Engineering, Electronics and Electrical.; Computer Science.
Degree Name:
M.S.
Degree Level:
masters
Degree Program:
Graduate College; Electrical and Computer Engineering
Degree Grantor:
University of Arizona
Advisor:
Kuo, Sy-Yen

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleEfficient covering of general polygons by rectanglesen_US
dc.creatorHsu, Yu-Cheng, 1966-en_US
dc.contributor.authorHsu, Yu-Cheng, 1966-en_US
dc.date.issued1990en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © 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.en_US
dc.description.abstractCovering 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.en_US
dc.typetexten_US
dc.typeThesis-Reproduction (electronic)en_US
dc.subjectComputer Science.en_US
dc.subjectEngineering, Electronics and Electrical.en_US
dc.subjectComputer Science.en_US
thesis.degree.nameM.S.en_US
thesis.degree.levelmastersen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorKuo, Sy-Yenen_US
dc.identifier.proquest1342658en_US
dc.identifier.bibrecord.b26592502en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.