Decomposing Rectilinear Figures into Rectangles

Simple item page
dc.contributor.authorChadha, Rituen
dc.contributor.authorAllison, Donald C. S.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:35:42Zen
dc.date.available2013-06-19T14:35:42Zen
dc.date.issued1988en
dc.description.abstractWe discuss the problem of decomposing rectilinear regions, with or without holes, into a minimum number of rectangles. There are two different problems 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-to the 5/2), where n is the number of vertices of the figure, whereas the covering problem is exponential in its time complexity.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000102/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000102/01/TR-88-17.pdfen
dc.identifier.trnumberTR-88-17en
dc.identifier.urihttp://hdl.handle.net/10919/19962en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleDecomposing Rectilinear Figures into Rectanglesen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-88-17.pdf
Size:
1.4 MB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports