This thesis discusses the problem of decomposing rectilinear regions, with or without holes, into a minimum number of rectangles. There are two different types of decomposition considered here : decomposing a figure into non-overlapping parts, called partitioning, and decomposing a figure into possibly overlapping parts, called covering. A method is outlined and proved for solving the above two problems, and algorithms for the solutions of these problems are presented. The partitioning problem can be solved in time O(n⁵ ²), where n is the number of vertices of the figure, whereas the covering problem is exponential in its time complexity. / M.S.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/90962 |
| Date | January 1987 |
| Creators | Chadha, Ritu |
| Contributors | Computer Science |
| Publisher | Virginia Polytechnic Institute and State University |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Thesis, Text |
| Format | ix, 116 leaves, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | OCLC# 17604740 |
Page generated in 0.013 seconds