Decomposing rectilinear regions into rectangles
| dc.contributor.author | Chadha, Ritu | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2019-07-03T16:42:47Z | en |
| dc.date.available | 2019-07-03T16:42:47Z | en |
| dc.date.issued | 1987 | en |
| dc.description.abstract | 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. | en |
| dc.description.degree | M.S. | en |
| dc.format.extent | ix, 116 leaves | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.uri | http://hdl.handle.net/10919/90962 | en |
| dc.language.iso | en_US | en |
| dc.publisher | Virginia Polytechnic Institute and State University | en |
| dc.relation.isformatof | OCLC# 17604740 | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.lcc | LD5655.V855 1987.C523 | en |
| dc.subject.lcsh | Decomposition (Mathematics) | en |
| dc.title | Decomposing rectilinear regions into rectangles | en |
| dc.type | Thesis | en |
| dc.type.dcmitype | Text | en |
| thesis.degree.discipline | Computer Science | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | M.S. | en |
Files
Original bundle
1 - 1 of 1