ÐÓ°ÉÔ­´´

ÐÓ°ÉÔ­´´ University
Technical Report TR-212
September 1992

Algorithms for Asymptotically Optimal Contained Rectangles and Triangles

Evangelos Kranakis & Emran Rafique

Abstract

We consider the problem of computing asymptotically maximal area rect­angles and triangles contained in simple polygons. We exhibit an algo-­ rithm which given an n-node polygon P, and a fixed integer k computes 2 2
in 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­tio 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­cient 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
0(n).

TR-212.pdf