{"id":14720,"date":"2022-05-26T22:04:54","date_gmt":"2022-05-27T02:04:54","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14720"},"modified":"2026-06-09T11:22:24","modified_gmt":"2026-06-09T15:22:24","slug":"tr-42-minimum-decompositions-of-polygonal-objects","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/tr-42-minimum-decompositions-of-polygonal-objects\/","title":{"rendered":"TR-42: Minimum Decompositions of Polygonal Objects"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-42: Minimum Decompositions of Polygonal Objects\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/\">Technical Report<\/a>&nbsp;<strong>TR-42<\/strong><br>March 1984<\/p>\n\n\n\n<h2 id=\"minimum-decompositions-of-polygonal-objects\" class=\"wp-block-heading\">Minimum Decompositions of Polygonal Objects<\/h2>\n\n\n\n<p>J. Mark Keil &amp; J\u00f6rg-R\u00fcdiger Sack<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Geometrical problems occur frequently in such areas as pattern recognition, image processing, computer graphics and VLSI. Given a geometrical problem an efficient solution is often dependent on the nature of the objects we are dealing with. Objects are often described by polygons. The usual strategy for solving many of these problems on general polygons is to decompose the polygon into simple component parts, solve the problem on each component using a specialized algorithm, and then combine the partial solutions.&nbsp; We survey the existing literature on minimum number and minimum edge-length decompositions. We also give an O(n4 ) algorithm to decompose a rectilinear polygon into the minimum numbers of convex quadrilaterals.<\/p>\n\n\n\n<h3 id=\"download\" class=\"wp-block-heading\">Download<\/h3>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-42.pdf\">TR-42.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-42March 1984 Minimum Decompositions of Polygonal Objects J. Mark Keil &amp; J\u00f6rg-R\u00fcdiger Sack Abstract Geometrical problems occur frequently in such areas as pattern recognition, image processing, computer graphics and VLSI. Given a geometrical problem an efficient solution is often dependent on the nature of the objects we are dealing with. Objects are often [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11787,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-14720","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14720","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14720"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14720\/revisions"}],"predecessor-version":[{"id":24559,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14720\/revisions\/24559"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11787"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14720"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}