{"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":"2022-06-16T20:26:36","modified_gmt":"2022-06-17T00:26:36","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":"

Carleton University
\nTechnical Report<\/a> TR-212<\/strong>
\nSeptember 1992<\/p>\n

Algorithms for Asymptotically Optimal Contained Rectangles and Triangles<\/h2>\n
Evangelos Kranakis & Emran Rafique<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

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
\nin polygon time 0( such n kthat log ln) :and 1, space ( 0( kP(:fn) 6a ,..) 2 ( rectangle 1 – 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
\n0(n).<\/p>\n

<\/div>\n

TR-212.pdf<\/a><\/p>\n