Carleton University
Technical Report TR-212
September 1992
Algorithms for Asymptotically Optimal Contained Rectangles and Triangles
Abstract
We consider the problem of computing asymptotically maximal area rectangles 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 ratio 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 efficient 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).