{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:29Z","timestamp":1740109589034,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212129"],"award-info":[{"award-number":["CCF-2212129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We describe a polynomial time algorithm that takes as input a polygon with axis-parallel sides but irrational vertex coordinates, and outputs a set of as few rectangles as possible into which it can be dissected by axis-parallel cuts and translations. The number of rectangles is the rank of the Dehn invariant of the polygon. The same method can also be used to dissect an axis-parallel polygon into a simple polygon with the minimum possible number of edges. When rotations or reflections are allowed, we can approximate the minimum number of rectangles to within a factor of two.<\/jats:p>","DOI":"10.1007\/s00454-023-00614-w","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T16:10:49Z","timestamp":1702397449000},"page":"129-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Orthogonal Dissection into Few Rectangles"],"prefix":"10.1007","volume":"73","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"issue":"8","key":"614_CR1","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1080\/00029890.2007.11920458","volume":"114","author":"D Benko","year":"2007","unstructured":"Benko, D.: A new approach to Hilbert\u2019s third problem. Am. Math. Mon. 114(8), 665\u2013676 (2007). https:\/\/doi.org\/10.1080\/00029890.2007.11920458","journal-title":"Am. Math. Mon."},{"key":"614_CR2","doi-asserted-by":"crossref","unstructured":"Bolyai, W.: Transmutatio figurarum quoad areas; et hinc reductio earum ad formam rectae. In: Tentamen iuventutem studiosam in elementa matheseos purae elementaris ac sublimioris methodo intuitiva evidentiaque huic propria introducendi, cum appendici triplici, vol. 2, pp. 60\u201363. Typis Collegii Reformatorum per Josephum et Simeonem Kali de felso Vist (1833). https:\/\/archive.org\/details\/tentamenjuventut02boly\/page\/60","DOI":"10.5479\/sil.273422.39088000381822"},{"issue":"5","key":"614_CR3","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1109\/32.6142","volume":"14","author":"Y Cheng","year":"1988","unstructured":"Cheng, Y., Iyengar, S.S., Kashyap, R.L.: A new method of image compression using irreducible covers of maximal rectangles. IEEE Trans. Softw. Eng. 14(5), 651\u2013658 (1988). https:\/\/doi.org\/10.1109\/32.6142","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"3","key":"614_CR4","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01448001","volume":"55","author":"M Dehn","year":"1901","unstructured":"Dehn, M.: Ueber den Rauminhalt. Math. Ann. 55(3), 465\u2013478 (1901). https:\/\/doi.org\/10.1007\/BF01448001","journal-title":"Math. Ann."},{"key":"614_CR5","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/BF01444289","volume":"57","author":"M Dehn","year":"1903","unstructured":"Dehn, M.: \u00dcber Zerlegung von Rechtecken in Rechtecke. Math. Ann. 57, 314\u2013332 (1903). https:\/\/doi.org\/10.1007\/BF01444289","journal-title":"Math. Ann."},{"key":"614_CR6","doi-asserted-by":"publisher","unstructured":"Dupont, J.L.: Scissors congruences, group homology and characteristic classes. In: Nankai Tracts in Mathematics, vol. 1. World Scientific Publishing, River Edge (2001). https:\/\/doi.org\/10.1142\/9789812810335","DOI":"10.1142\/9789812810335"},{"issue":"9","key":"614_CR7","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1016\/j.dam.2008.12.008","volume":"157","author":"K Engel","year":"2009","unstructured":"Engel, K.: Optimal matrix-segmentation by rectangles. Discret. Appl. Math. 157(9), 2015\u20132030 (2009). https:\/\/doi.org\/10.1016\/j.dam.2008.12.008","journal-title":"Discret. Appl. Math."},{"key":"614_CR8","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: Graph-theoretic solutions to computational geometry problems. In: Paul, C., Habib, M. (eds.) Graph-Theoretic Concepts in Computer Science, 35th International Workshop, WG 2009, Montpellier, France, 24\u201326 June 2009, Revised Papers. Lecture Notes in Computer Science, vol. 5911, pp. 1\u201316. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-11409-0_1","DOI":"10.1007\/978-3-642-11409-0_1"},{"issue":"1","key":"614_CR9","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0734-189X(84)90139-7","volume":"28","author":"L Ferrari","year":"1984","unstructured":"Ferrari, L., Sankar, P.V., Sklansky, J.: Minimal rectangular partitions of digitized blobs. Comput. Vis. Graph. Image Process. 28(1), 58\u201371 (1984). https:\/\/doi.org\/10.1016\/0734-189X(84)90139-7","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"614_CR10","doi-asserted-by":"publisher","unstructured":"Frederickson, G.N.: Dissections: Plane & Fancy. Cambridge University Press, Cambridge (1997). For the Greek Cross to Square Dissection, see pp. 105\u2013106. https:\/\/doi.org\/10.1017\/CBO9780511574917","DOI":"10.1017\/CBO9780511574917"},{"key":"614_CR11","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1515\/crll.1833.10.228","volume":"10","author":"P Gerwien","year":"1833","unstructured":"Gerwien, P.: Zerschneidung jeder beliebigen Anzahl von gleichen geradlinigen Figuren in dieselben St\u00fccke. J. Reine Angew. Math. 10, 228\u2013234 (1833). https:\/\/doi.org\/10.1515\/crll.1833.10.228","journal-title":"J. Reine Angew. Math."},{"key":"614_CR12","volume-title":"Tilings and Patterns","author":"B Gr\u00fcnbaum","year":"1989","unstructured":"Gr\u00fcnbaum, B., Shephard, G.C.: Tilings and Patterns. W. H. Freeman, New York (1989)"},{"key":"614_CR13","doi-asserted-by":"publisher","unstructured":"Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus. Springer Series in Computational Mathematics, vol. 42. Springer, Berlin (2012). See in particular the identification of matrices with tensors on pp. 5, and 55\u201356, and the equivalence of multiple definitions of matrix rank on p. 23. https:\/\/doi.org\/10.1007\/978-3-642-28027-6","DOI":"10.1007\/978-3-642-28027-6"},{"key":"614_CR14","doi-asserted-by":"publisher","unstructured":"Hannenhalli, S., Hubbell, E., Lipshutz, R., Pevzner, P.A.: Combinatorial algorithms for design of DNA arrays. In: Chip Technology. Advances in Biochemical Engineering\/Biotechnology, vol. 77, pp. 1\u201319. Springer, Berlin (2002). https:\/\/doi.org\/10.1007\/3-540-45713-5_1","DOI":"10.1007\/3-540-45713-5_1"},{"issue":"4","key":"614_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.2307\/2370498","volume":"34","author":"WH Jackson","year":"1912","unstructured":"Jackson, W.H.: Wallace\u2019s theorem concerning plane polygons of the same area. Am. J. Math. 34(4), 383\u2013390 (1912). https:\/\/doi.org\/10.2307\/2370498","journal-title":"Am. J. Math."},{"key":"614_CR16","unstructured":"Jain, P., Meka, R., Dhillon, I.S.: Guaranteed rank minimization via singular value projection. In: Lafferty, J.D., Williams, C.K.I., Shawe-Taylor, J., Zemel, R.S., Culotta, A. (eds.) Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a Meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pp. 937\u2013945. Curran Associates, Inc., Red Hook (2010). https:\/\/proceedings.neurips.cc\/paper\/2010\/hash\/08d98638c6fcd194a4b1e6992063e944-Abstract.html"},{"issue":"2","key":"614_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7146\/math.scand.a-10888","volume":"22","author":"B Jessen","year":"1968","unstructured":"Jessen, B.: The algebra of polyhedra and the Dehn\u2013Sydler theorem. Math. Scand. 22(2), 241\u2013256 (1968). https:\/\/doi.org\/10.7146\/math.scand.a-10888","journal-title":"Math. Scand."},{"issue":"1","key":"614_CR18","doi-asserted-by":"publisher","first-page":"R89","DOI":"10.37236\/178","volume":"16","author":"T Kalinowski","year":"2009","unstructured":"Kalinowski, T.: A dual of the rectangle-segmentation problem for binary matrices. Electron. J. Combin. 16(1), R89 (2009)","journal-title":"Electron. J. Combin."},{"key":"614_CR19","doi-asserted-by":"publisher","unstructured":"Karavelas, M.I.: Exact geometric and algebraic computations in CGAL. In: Fukuda, K., van\u00a0der Hoeven, J., Joswig, M., Takayama, N. (eds.) Mathematical Software\u2014ICMS 2010, 3rd International Congress on Mathematical Software, Kobe, Japan, 13\u201317 September 2010, Proceedings. Lecture Notes in Computer Science, vol. 6327, pp. 96\u201399. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-15582-6_20","DOI":"10.1007\/978-3-642-15582-6_20"},{"key":"614_CR20","doi-asserted-by":"publisher","unstructured":"Li, G., Zhang, H.: A rectangular partition algorithm for planar self-assembly. In: Proc. IEEE\/RSJ Int. Conf. Intelligent Robots and Systems, pp. 3213\u20133218 (2005). https:\/\/doi.org\/10.1109\/IROS.2005.1545324","DOI":"10.1109\/IROS.2005.1545324"},{"key":"614_CR21","doi-asserted-by":"publisher","first-page":"245","DOI":"10.3233\/FI-1978-2116","volume":"2","author":"W Lipski Jr","year":"1979","unstructured":"Lipski, W., Jr., Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two-dimensional data organization II. Fundam. Inf. 2, 245\u2013260 (1979). https:\/\/doi.org\/10.3233\/FI-1978-2116","journal-title":"Fundam. Inf."},{"key":"614_CR22","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-7091-6280-4_16","volume-title":"Symbolic Algebraic Methods and Verification Methods","author":"K Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Schirra, S.: Exact computation with leda_real\u2014theory and geometric applications. In: Alefeld, G., Rohn, J., Rump, S., Yamamoto, T. (eds.) Symbolic Algebraic Methods and Verification Methods, pp. 163\u2013172. Springer, Berlin (2001). https:\/\/doi.org\/10.1007\/978-3-7091-6280-4_16"},{"key":"614_CR23","unstructured":"Ohtsuki, T.: Minimum dissection of rectilinear regions. In: Proc. IEEE Int. Symp. Circuits and Systems, pp. 1210\u20131213 (1982)"},{"issue":"3","key":"614_CR24","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0010-4485(77)90118-X","volume":"9","author":"K Patel","year":"1977","unstructured":"Patel, K.: Computer-aided decomposition of geometric contours into standardized areas. Comput. Aided Des. 9(3), 199\u2013203 (1977). https:\/\/doi.org\/10.1016\/0010-4485(77)90118-X","journal-title":"Comput. Aided Des."},{"issue":"5","key":"614_CR25","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02187806","volume":"5","author":"MS Paterson","year":"1990","unstructured":"Paterson, M.S., Yao, F.F.: Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom. 5(5), 485\u2013503 (1990). https:\/\/doi.org\/10.1007\/BF02187806","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"614_CR26","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/4145269","volume":"111","author":"J Spandaw","year":"2004","unstructured":"Spandaw, J.: Dissecting cuboids into cuboids. Am. Math. Mon. 111(5), 425\u2013429 (2004). https:\/\/doi.org\/10.2307\/4145269","journal-title":"Am. Math. Mon."},{"key":"614_CR27","doi-asserted-by":"publisher","unstructured":"Stillwell, J.: 5.6: the Dehn invariant. In: Numbers and Geometry. Undergraduate Texts in Mathematics, pp. 161\u2013165. Springer, Berlin (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0687-3","DOI":"10.1007\/978-1-4612-0687-3"},{"key":"614_CR28","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/bf02564364","volume":"40","author":"J-P Sydler","year":"1965","unstructured":"Sydler, J.-P.: Conditions n\u00e9cessaires et suffisantes pour l\u2019\u00e9quivalence des poly\u00e8dres de l\u2019espace euclidien \u00e0 trois dimensions. Comment. Math. Helv. 40, 43\u201380 (1965). https:\/\/doi.org\/10.1007\/bf02564364","journal-title":"Comment. Math. Helv."},{"key":"614_CR29","unstructured":"Wallace, W., Lowry, J.: Question 269. In: Leybourn, T. (ed.) New Series of the Mathematical Repository, vol. 3, pp. 44\u201346. W. Glendinning, London (1814). https:\/\/archive.org\/details\/mathematicalrep00leybgoog\/page\/n54"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00614-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00614-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00614-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T03:02:23Z","timestamp":1736218943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00614-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["614"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00614-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"1 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}