Show simple item record

dc.contributor.authorChadha, Rituen_US
dc.contributor.authorAllison, Donald C. S.en_US
dc.date.accessioned2013-06-19T14:35:42Z
dc.date.available2013-06-19T14:35:42Z
dc.date.issued1988
dc.identifierhttp://eprints.cs.vt.edu/archive/00000102/en_US
dc.identifier.urihttp://hdl.handle.net/10919/19962
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_US
dc.format.mimetypeapplication/pdfen_US
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen_US
dc.relation.ispartofHistorical Collection(Till Dec 2001)en_US
dc.titleDecomposing Rectilinear Figures into Rectanglesen_US
dc.typeTechnical reporten_US
dc.identifier.trnumberTR-88-17en_US
dc.type.dcmitypeTexten_US
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000102/01/TR-88-17.pdf


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record