{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:31Z","timestamp":1787340571379,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>The problem of decomposing a polygon into simpler components is of interest in fields such as computational geometry, syntactic pattern recognition, and graphics. In this paper we consider decompositions which do not introduce Steiner points. The simpler components we consider are convex polygons, spiral polygons, star-shaped polygons and monotone polygons. We apply a technique for improving the efficiency of dynamic programming algorithms in order to achieve polynomial time algorithms for the problems of decomposing a simple polygon into the minimum number of each of the component types. Using the same technique we are able to exhibit polynomial time algorithms for the problems of decomposing a simple polygon into each of the component types while minimizing the length of the internal edges used to form the decomposition. When the polygons are allowed to contain holes many of the problems become NP-hard.<\/jats:p>","DOI":"10.1137\/0214056","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"799-817","source":"Crossref","is-referenced-by-count":117,"title":["Decomposing a Polygon into Simpler Components"],"prefix":"10.1137","volume":"14","author":[{"given":"J. Mark","family":"Keil","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90002-9"},{"key":"R2","volume-title":"Dynamic programming","author":"Bellman Richard","year":"1957"},{"key":"R3","unstructured":"K. Q. Brown,  Dynamic programming in computer science, Report, CMU-CS-79-106, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh,  1979"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804396"},{"key":"R5","unstructured":"B. Chazelle, Ph.D. Thesis,  Computational geometry and convexity, Yale Univ., New Haven, CT,  1980"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9.50009-8"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90019-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90066-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224276"},{"key":"R10","unstructured":"D. Greene,  The decomposition of polygons into convex parts,  1982, Manuscript, Xerox Parc"},{"key":"R11","unstructured":"D. Greene,  1982, Private communication"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(75)90151-5"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0115060"},{"key":"R14","unstructured":"J. M. Keil, Ph.D. Thesis,  Decomposing polygons into simpler components, Univ. Toronto, Toronto,  1983"},{"key":"R15","volume-title":"Computational Geometry","author":"Keil J. M.","year":"1984"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0206043"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012784"},{"key":"R19","unstructured":"A. Lingas, R. Pinter, R. Rivest, A. Shamir,  Minimum edge length decompositions of rectilinear figures,  1981, unpublished manuscript, MIT"},{"key":"R20","first-page":"245","volume":"2","author":"Lipski W.","year":"1978","journal-title":"Fund. Inform. (4)"},{"key":"R21","volume-title":"Principles of Interactive Computer Graphics","author":"Newman W.","year":"1979"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(68)90006-X"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90091-0"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675001"},{"key":"R26","unstructured":"G. T. Toussaint,  Pattern recognition and geometrical complexity,  Proc. Fifth International Conference on Pattern Recognition, Miami Beach,  1980,  1324\u20131347"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:51Z","timestamp":1787337591000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214056"],"URL":"https:\/\/doi.org\/10.1137\/0214056","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}