{"id":15054,"date":"2022-06-16T20:26:36","date_gmt":"2022-06-17T00:26:36","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15054"},"modified":"2026-06-08T15:36:07","modified_gmt":"2026-06-08T19:36:07","slug":"tr-212-algorithms-for-asymptotically-optimal-contained-rectangles-and-triangles","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/tr-212-algorithms-for-asymptotically-optimal-contained-rectangles-and-triangles\/","title":{"rendered":"TR-212: Algorithms for Asymptotically Optimal Contained Rectangles and Triangles"},"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-212: Algorithms for Asymptotically Optimal Contained Rectangles and Triangles\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-1992\/\">Technical Report<\/a>&nbsp;<strong>TR-212<\/strong><br>September 1992<\/p>\n\n\n\n<h2 id=\"algorithms-for-asymptotically-optimal-contained-rectangles-and-triangles\" class=\"wp-block-heading\">Algorithms for Asymptotically Optimal Contained Rectangles and Triangles<\/h2>\n\n\n\n<p>Evangelos Kranakis &amp; Emran Rafique<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>We consider the problem of computing asymptotically maximal area rect\u00adangles and triangles contained in simple polygons. We exhibit an algo-\u00ad rithm which given an n-node polygon P, and a fixed integer k computes 2 2<br>in polygon time 0( such n kthat log ln) :and 1, space ( 0( kP(:fn) 6a ,..) 2 ( rectangle 1 \u2013 p()kRa1g ) , where contained Rma:r in theis the maximal area rectangle contained in the polygon and p( P) is the ra\u00adtio of the polygon (i.e. the quotient of its length over its width). The same algorithm has time complexity 0( nk2 ) on convex polygons. A more effi\u00adcient algorithm with time complexity 0(nk) can also be given for objects of the same similarity type ( e.g. squares, equilateral triangles, and more generally similar triangles) contained in convex polygons. A similar result with time complexity 0( n3 k3 log n) can be proved for arbitrary triangles contained in simple polygons. All our algorithms have space complexity<br>0(n).<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-212.pdf\">TR-212.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-212September 1992 Algorithms for Asymptotically Optimal Contained Rectangles and Triangles Evangelos Kranakis &amp; Emran Rafique Abstract We consider the problem of computing asymptotically maximal area rect\u00adangles and triangles contained in simple polygons. We exhibit an algo-\u00ad rithm which given an n-node polygon P, and a fixed integer k computes 2 2in polygon time [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11910,"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":[],"class_list":["post-15054","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15054","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=15054"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15054\/revisions"}],"predecessor-version":[{"id":24480,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15054\/revisions\/24480"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11910"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15054"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15054"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}