{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:18Z","timestamp":1787340798777,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:p>We solve the problem of decomposing a rectangle R into p rectangles of equal area so that the maximum rectangle perimeter is as small as possible. This work has applications in areas such as flexible object packing and data allocation. Our solution requires only a constant number of arithmetic operations and integer square roots to characterize the decomposition, and linear time to print the decomposition. The discrete analogue of the problem in which the rectangle R is replaced by a rectangular array of lattice points is also considered, and three heuristic methods of solution are given. All of the heuristic methods operate by finding a discrete approximation to our optimal decomposition of R, but with different tradeoffs between the accuracy of the approximation and running time.<\/jats:p>","DOI":"10.1137\/0217077","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"1215-1231","source":"Crossref","is-referenced-by-count":13,"title":["The Decomposition of a Rectangle into Rectangles of Minimal Perimeter"],"prefix":"10.1137","volume":"17","author":[{"given":"T. Y.","family":"Kong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A. W.","family":"Roscoe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187679"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90002-9"},{"key":"R3","volume-title":"Graphs and hypergraphs","author":"Berge Claude","year":"1973"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804396"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. S. Franzblau, D. J. Kleitman,  An algorithm for constructing regions with rectangles: independence and minimum generating sets for collections of intervals,  Proc. 16th Annual ACM Symposium on Theory of Computing, Washington, D.C.,  1984,  167\u2013174","DOI":"10.1145\/800057.808678"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"R8","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"T. Gonzalez, S.Q. Zheng,  Bounds for partitioning rectilinear polygons,  Proc. Symposium on Computational Geometry,  1985,  281\u2013287","DOI":"10.1145\/323233.323269"},{"key":"R10","volume-title":"The theory of graphs and its applications","author":"Berge Claude","year":"1962"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90817-7"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. Karp, M. Luby, A. Marchetti-Spaccamela,  Probabilistic analysis of multidimensional bin packing problems,  Proc. 16th Annual ACM Symposium on Theory of Computing,  1984,  289\u2013298","DOI":"10.1145\/800057.808693"},{"key":"R13","unstructured":"S. Kasif, R. Klette,  A data allocation problem for SIMD computers, Tech. Report, CAR-TR-11, Center for Automation Research, University of Maryland, College Park, MD,  1983"},{"key":"R14","unstructured":"T. Y. Kong, D. M. Mount, A. W. Roscoe,  The decomposition of a rectangle into rectangles of minimal perimeter, Tech. Report, CAR-TR-169, Center for Automation Research, College Park, MD,  1986"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90061-8"},{"key":"R16","volume-title":"Convex sets and their applications","author":"Lay Steven R.","year":"1982"},{"key":"R17","unstructured":"J. O'Rourke,  The complexity of computing minimum convex conveys for polygons,  Proc. 20th Annual Allerton Conference on Communications, Control and Computing, Urbana, IL,  1982,  75\u201384"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:47Z","timestamp":1787338127000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["10.1137\/0217077"],"URL":"https:\/\/doi.org\/10.1137\/0217077","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}