Approximation of convex figures by pairs of rectangles

Abstract

We consider the problem of approximating a convex figure in the plane by a pair (r,R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R, We show the existence of such a pair where the sides of the outer rectangle are at most twice as long as the sides of the inner rectangle, thereby solving a problem posed by Polya and Szego. If the n vertices of a convex polygon C are given as a sorted array, such an approximating pair of rectangles can be computed in time O(log(2)n). (C) 1998 Elsevier Science B.V.